Trải qua những cuộc thi ICPC, và cả những cuộc tình dang dở, lúc về già, coder Luna đã để dành được một kho châu báu quý giá của cả cuộc đời mình. Cụ ấy đã cẩn thận chôn nó vào cái hộp tròn bán kính ~1~ ở một khu rừng hoang vắng. Tuy nhiên, một ngày nọ, các nhà thám hiểm từ CLB H3.2 đã lần mò ra dấu vết kho báu này, vì họ nghe tương truyền rằng trong kho báu đó, có chứa nhiều bí kíp thượng thừa, code đâu AC đó, rõ ràng là một loại vũ khí cực mạnh. Mỗi nhà thám hiểm sẽ có một máy định vị, chấm ra ba điểm trong bề mặt khu rừng và nối lại thành tam giác. Nếu cái hộp và miền mặt phẳng chứa tam giác có điểm chung nào đó (kể cả trường hợp cạnh của tam giác chạm vào cái hộp) thì máy sẽ phát ra tiếng Bíp bíp bíp. Hãy giúp coder già Luna xem những kẻ tò mò có tìm được kho châu báu này không nhé?

Input

Dòng đầu tiên chứa số ~t~ với ~1 \le t \le 3~ cho biết số nhà thám hiểm. Ba dòng tiếp theo, mỗi dòng chứa ~6~ số nguyên là tọa độ các điểm mà máy dò tìm chấm lên. Cho biết rằng chúng không thẳng hàng và giá trị tuyệt đối không vượt quá ~100.~ Chú ý rằng tâm của cái hộp hình tròn trùng với gốc tọa độ.

Output

Ứng với mỗi nhà thám hiểm, in ra YES / NO ứng với việc họ có tìm được châu báu hay không?

Sample input 1

2
1 1 -1 2 3 2
1 0 2 0 1 -1

Sample output 1

NO
YES

Sample input 2

2
-2 -1 -2 2 1 -2
0 0 1 1 3 1

Sample output 2

YES
YES

Giải thích: tham khảo thêm các hình vẽ minh họa.

Trong mùa giải ICPC 2023 mới, nhân lực của CLB H3.2 khá đông và hung hãn. Có tất cả ~n~ thành viên và mỗi người có một điểm số năng lực nhất định (tất nhiên có thể có nhiều người có cùng điểm số năng lực). Thầy Tina muốn các bạn tạo với nhau thành các team ba người, trong đó hai thành viên bất kỳ cùng team thì chênh lệch điểm số năng lực không quá ~2.~ Hãy giúp thầy Tina tính xem có bao nhiêu team khác nhau có thể được tạo ra?

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~3 \le n \le 10^5.~

Dòng tiếp theo gồm điểm số năng lực của các thành viên, có giá trị nguyên dương không vượt quá ~10^9.~

Output

Số team có thể tạo thành.

Sample input 1:

4
11 12 13 14

Sample output 1:

2

Sample input 2:

5
1 1 1 1 1

Sample output 2:

10

Giải thích: trong VD1, ta thấy các bạn có số thứ tự ~(1,2,3)~ và ~(2,3,4)~ có thể cùng team với nhau; còn trong VD2, ta thấy ba bạn bất kỳ đều có thể tạo thành team, số cách chọn là ~C_5^3 = 10~.

Công ty IUHCoder tuy có các thành viên không cùng lớp, cùng Khoa nhưng lại rất đoàn kết và hoạt động rất chăm chỉ. Mỗi người trong cty có một năng lượng tích cực, được cho bởi một số nguyên. Năng lượng tích cực của một nhóm sẽ bằng năng lượng tích cực của những người trong nhóm đó nhân lại với nhau. Vì sự đoàn kết nên có không quá một thành viên có năng lượng tích cực bị âm thôi, còn lại thì đều là các số không âm. Mỗi buổi họp của cty, các thành viên sẽ ngồi vào một dãy bàn và CEO Tina sẽ cùng bàn bạc các kế hoạch chiến lược. Tuy nhiên, gần đây có một số task bị chậm trễ tiến độ. Vì thế CEO muốn chọn ra một nhóm các bạn ngồi liên tiếp trong dãy bàn (nhóm này có ít nhất một người) mà giá trị năng lượng tích cực của nhóm đó là nhỏ nhất. CEO muốn làm việc riêng với các bạn này, tìm hiểu nguyên nhân xem thế nào. Hãy giúp CEO tính ra giá trị nhỏ nhất đó nhé.

Input

Dòng đầu tiên gồm số ~n~ cho biết số thành viên của công ty, trong đó ~1 \le n \le 10^5~. Dòng tiếp theo cho biết năng lượng tích cực của mỗi người, là các số nguyên có giá trị tuyệt đối không quá ~10^6.~

Output

Đáp số của bài toán, lấy số dư khi chia cho ~10^9+7~, số dư này sẽ nằm trong khoảng giá trị ~0,1,...,10^9+6.~

Sample input 1:

3
1 2 3

Sample output 1:

1

Sample input 2:

3
0 2 3

Sample output 2:

0

Sample input 3:

3
-1 2 3

Sample output 3:

1000000001

Giải thích: giá trị nhỏ nhất trong VD1 và VD2 là dễ thấy, còn trong VD3, ta thấy nếu lấy tích cả ba năng lượng tích cực thì ra được ~-6~, số dư cần tìm sẽ là ~10^9+1.~

Codecamp là một hoạt động không thể thiếu của các coder tại IUH, đó là dịp mà các bạn sẽ tách khỏi trường, đi đến một nơi thật xa, và chỉ để code. Có lần thì đi Đà Lạt ngắm hoàng hôn, có lần đi Vũng Tàu bắt cá, hoặc lên Măng Đen ngắm suối chảy róc rách, ... Và trong một chuyến codecamp như thế của CLB H3.2, các thành viên thuê xe máy để đi tham quan các địa điểm. Có tất cả ~n~ địa điểm để thăm và giữa chúng có ~m~ con đường một chiều cho xe máy chạy qua được (nghĩa là có đường đi từ ~A~ đến ~B~ thì chưa chắc có đường từ ~B~ về ~A~), trong đó có ~k~ địa điểm có phục vụ ăn uống. Các coder của H3.2 muốn xen kẽ giữa chuyến đi chơi sẽ có các buổi ăn uống, thư giãn. Vì thế các coder muốn biết rằng từ mỗi địa điểm trong ~n~ địa điểm thì khoảng cách ngắn nhất đến một địa điểm ăn uống nào đó là bao nhiêu (khoảng cách ở đây là số con đường một chiều mà bạn ấy cần phải đi qua).

Input

Dòng đầu tiên gồm các số ~n,m,k~ cho biết số địa điểm, số đường đi và số địa điểm đặc biệt, trong đó ~2 \le n \le 10^5~, ~0 \le m \le 10^6~ (các đường đi có thể bị lặp lại) và ~0 \le k \le n.~ Dòng thứ hai gồm danh sách các địa điểm ăn uống, mỗi giá trị sẽ từ ~1~ đến ~n~, phân biệt nhau. Trong ~m~ dòng tiếp theo sẽ có các thông tin con đường đi giữa từ địa điểm ~u \to v~ nào đó với ~1 \le u \neq v \le n~.

Output

Một dòng duy nhất gồm ~n~ khoảng cách từ địa điểm ~1,2,...,n~ đến chỗ có thể ăn uống gần nhất.

Sample input 1

5 4 2
1 5
1 2
2 3
3 4
4 5

Sample output 1

0 3 2 1 0

Sample input 2

5 4 2
1 5
2 1
2 3
3 4
5 4

Sample output 2

0 1 -1 -1 0

Giải thích: trong VD1, ta thấy địa điểm ~1,5~ đã là đặc biệt nên không cần di chuyển gì, còn từ địa điểm ~2,3,4~ có thể đi đến địa điểm ~5~ với độ dài đường đi lần lượt là ~3,2,1;~ trong VD2, ta thấy tương tự trên nhưng địa điểm ~2~ đến được địa điểm ~1~ qua ~1~ bước, còn địa điểm ~3,4~ thì không đến được ~1~ hoặc ~5~ bằng cách nào cả.

Trong ngày cuối cùng trước khi học kỳ mới bắt đầu, CLB H3.2 có tổ chức một Vũ hội, trong đó các thành viên sẽ múa hát xuyên màn đêm. Để buổi Vũ hội thêm rực rỡ, Ban tổ chức đã lắp thêm ~n~ bóng đèn trang trí vào khắp phòng, và các bóng đèn được đánh số từ ~1~ đến ~n~. Có tất cả ~6~ công tắc với các tính năng như sau:

• Công tắc 1: thay đổi trạng thái tất cả các bóng đèn (từ bật thành tắt, tắt thành bật).
• Công tắc 2: cũng thay đổi trạng thái nhưng chỉ với các bóng có số thứ tự chẵn.
• Công tắc 3: cũng thay đổi trạng thái với các bóng có số thứ tự lẻ.
• Công tắc 4: cũng thay đổi trạng thái với các bóng có số thứ tự chia hết cho ~3~.
• Công tắc 5: cũng thay đổi trạng thái với các bóng có số thứ tự chia ~3~ dư ~1~.
• Công tắc 6: cũng thay đổi trạng thái với các bóng có số thứ tự chia ~3~ dư ~2~.

Ban đầu, tất cả bóng đèn đều bật. Trong buổi tiệc, DJ Banana sẽ lo việc điều phối âm nhạc và bật tắt các công tắc để không khí thêm phần mờ ảo. Đến cuối buổi tiệc, Banana mắt lim dim đếm được có ~m~ bóng đèn còn bật (các bóng còn lại chưa rõ bật hay tắt) và đếm được rằng đã bấm công tắc tổng cộng ~c~ lần. Hỏi có thể có bao nhiêu khả năng xảy ra đối với ~n~ bóng đèn của đêm Vũ hội?

Input

Một dòng duy nhất gồm số bóng đèn ~n~ với ~1 \le n \le 10^5~, số bóng đèn còn bật mà Banana đã thấy được là ~m~ với ~0 \le m \le n~ và tổng số lần ấn công tắc ~c~ với ~0 \le c \le 10^9~.

Dòng tiếp theo cho biết số thứ tự của các bóng đèn còn bật mà Ban thấy được (chú ý một lần nữa rằng các bóng còn lại thì không rõ là bật hay tắt).

Output

Số tất cả trạng thái có thể có thể (kết quả này vẫn tính được trong kiểu Int64).

Sample input 1:

4 2 1
1 2

Sample output 1:

1

Sample input 2:

8 2 100
1 5

Sample output 2:

4

Giải thích: trong VD1, ta thấy ở cuối cùng còn bóng đèn ~1,2~ còn bật, các bóng ~3,4~ chưa rõ trạng thái, ngoài ra được nhấn công tắc ~1~ lần. Như thế thì có thể nhấn công tắc ~4~ một lần và bóng có STT chia hết cho ~3~ sẽ tắt, lúc đó các bóng còn bật là ~1,2,4~, dễ thấy không còn trạng thái nào khác có thể thu được. Trong VD2, ta có một trong các cách là bật tắt công tắc 1 tất cả ~100~ lần, khi đó cuối cùng tất cả bóng đèn đều bật (nên rõ ràng trong đó có bóng ~1,5~ cũng còn bật).

Đức Tài là một đại gia angel investor của công ty IUHCoder. Cty này có ~n > 1~ thành viên và trong tháng tới, có 2 dự án cần hoàn thành. Để khuyến khích cho công việc, đại gia đã mang đến 2 túi vàng, mỗi túi có ~n~ đồng vàng để phát cho các thành viên trong dự án. Trong dự án 1, đại gia dự kiến sẽ thưởng cho top ~x~ nhân viên xuất sắc nhất trong cty, mỗi người một số tiền giống nhau. Cũng tương tự với dự án 2, đại gia thưởng cho top ~y~ nhân viên xuất sắc nhất trong cty, mỗi người một số tiền giống nhau trong đó ~x \neq y~. Đại gia thắc mắc là nên chọn ~x, y~ thế nào để chênh lệch tiền thưởng giữa hai lần là ít nhất, hãy giúp đại gia tính ra con số đó nhé. Ngày xưa đại gia cũng code giỏi lắm nhưng từ lúc lo kinh doanh thì bỏ code hẳn rồi.

Input

Một số nguyên dương duy nhất là ~n~ với ~2 \le n \le 10^{14}.~

Output

Chênh lệch tiền thưởng ít nhất.

Sample input 1

15

Sample output 1

2

Sample input 2

100

Sample output 2

1

Giải thích: trong VD1, ta có thể chọn ~(x,y)=(3,5)~ thì số tiền thưởng lần lượt là ~5,3~ với chênh lệch là ~2.~ Còn trong VD2, ta có thể chọn ~(x,y)=(25,20)~ thì số tiền thưởng lần lượt là ~4,5~ với chênh lệch là ~1.~

Ta biết rằng tình yêu không có tính đối xứng, nghĩa là ~P~ yêu ~M~ nhưng chưa chắc ~M~ yêu ~P~ (hoặc ~M~ yêu ~P~ nhưng chưa chắc ~P~ yêu ~M~); càng không có tính bắc cầu. Tuy nhiên, tình yêu giữa ~n~ coder trong H3.2 khá đặc biệt, lại có tính bắc cầu (nhưng vẫn không đối xứng nhé): nếu ~A~ yêu ~B~ và ~B~ yêu ~C~ thì ~A~ cũng sẽ yêu ~C~. Chú ý rằng đôi khi coder còn yêu chính bản thân họ. Tình yêu này rất trong sáng, giống như tình yêu quê hương đất nước vậy. Nhưng thầy Luna thấy các coder nhà mình lo yêu đương nhiều mà chưa tập trung vào ôn luyện nên một ngày nọ, thầy lục soát Messenger của các học trò và phát hiện được tất cả ~m~ đoạn tin nhắn thổ lộ tình cảm mà em này gửi cho em kia. Thầy biết rằng mình vẫn còn bỏ sót vài cặp nữa, vì tính chất bắc cầu trong tình yêu lạ lùng của CLB này, hãy giúp thầy tính ra số cặp đó nhé.

Input

Dòng đầu tiên gồm số nguyên dương ~n, m~ với ~1 \le n \le 689~ và ~1 \le m \le 5 \cdot 10^5.~

Trong ~m~ dòng tiếp theo, sẽ có cặp số ~u,v~ cho biết ~u~ đã có gửi tin nhắn cho ~v~, trong đó ~1 \le u, v \le n~, số ~u,v~ có thể trùng nhau và các cặp ~(u,v)~ có thể bị lặp lại.

Output

Hãy giúp thầy Luna đếm xem tổng cộng có bao nhiêu cặp yêu nhau trong CLB nhé.

Sample input 1

3 3
1 2
2 3
2 1

Sample input 1

6

Sample input 2

4 3
1 2
2 3
3 4

Sample input 2

6

Giải thích ta thấy rằng trong VD1, cặp ~(1,2)~ và ~(2,3)~ yêu nhau nên theo bắc cầu thì ~(1,3)~ cũng yêu nhau, cặp ~(1,2)~ và ~(2,1)~ yêu nhau nên cặp ~(1,1)~ cũng yêu nhau, tương tự cặp ~(2,1)~ và ~(1,2)~ yêu nhau nên cặp ~(2,2)~ cũng thế, có tất cả ~6~ cặp (gồm ~3~ cặp đã biết và ~3~ cặp mà thầy Luna suy luận thêm). Trong VD2, trước hết ta cũng suy ra có cặp ~(1,3)~ và cặp ~(2,4)~, nhưng cặp ~(1,3)~ kết hợp với ~(3,4)~ thì sẽ thêm cặp ~(1,4)~ nữa, vì thế vẫn có ~6~ cặp.

Theo lời đồn trong giới làm đề, vấn đề sau đây chỉ đơn giản là một vấn đề sắp xếp mà thôi. Vì thế nên !!! quyết định giao cho bạn yêu cầu này để khởi động và lấy tinh thần: cho một danh sách gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Hãy cho !!! biết số lớn nhất có thể tạo ra băng cách xếp lại và ghép các số đó theo thứ tự từ trái sang phải.

Input:

• Dòng đầu tiên chứa một số nguyên dương ~1 \le n \le 10^5~;
• Dòng thứ hai chứa số ~n~ số nguyên dương ~a_i~ với ~1 \le a_i \le 10^{9}~.

Output:

• Một dòng duy nhất chứa một số nguyên lớn nhất mà được tạo ra theo yêu cầu của !!!.

Sample input:

4
123 71 5 9

Sample output:

9715123

Giải thích: danh sách gồm các số: [~123, 71, 5, 9~], thì số lớn nhất có thể tạo ra từ các số đố là: ~9715123~ theo danh sách đã được xếp lại là [~9, 71, 5, 123~].

Cho ~2~ số nguyên dương ~a,b~ với ~a \le b.~ Hãy đếm có bao nhiêu chữ số ~0~ (không) ở trong các số thuộc đoạn từ ~a~ đến ~b~.

Nếu kết quả thu được quá lớn thì các bạn hãy chia dư cho ~10^9+7~ nhé.

Input:

• Dòng đầu tiên chứa ~2~ số nguyên dương ~a~ và ~b~ với ~1 \le a \le b \le 10^{10^5}~.

Output:

• Số lượng số ~0~ trong đoạn từ ~a~ đến ~b~ và chia dư cho ~10^9+7~.

Sample input 1:

10 20

Sample output 1:

2

Sample input 2:

100 110

Sample output 2:

12

Giải thích

Ví dụ 1: Ta có ~2~ số ~a = 10~ và ~b = 20~. Vậy dãy cần xét gồm có các số là ~[10, 11, 12, 13, 14, 15 ,16, 17, 18, 19, 20]~ thì có ~11~ chứa chữ số ~0~ và số lượng chữ số ~0~ mà mỗi số chứa là ~[10~ ~(~chứa ~1~ chữ số ~0)~, ~20~ ~(~chứa ~1~ chữ số ~0)]~ . Vậy tổng số chữ số ~0~ là ~S = 1 + 1 = 2~ chữ số ~0~.

Ví dụ 2: Ta có ~2~ số ~a = 100~ và ~b = 110~. Vậy dãy cần xét gồm có các số là ~[100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110]~ thì có ~11~ chứa chữ số ~0~ và số lượng chữ số ~0~ mà mỗi số chứa là ~S = 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 12~ chữ số ~0~.

Cho một số nguyên dương ~n~. Mỗi thao tác cho phép chuyển chữ số đầu tiên từ trái sang xuống cuối (cho phép có chữ số ~0~ đứng đầu). Hỏi nếu được thực hiện tối đa ~k~ thao tác thì có cách nào thu được một số chia hết cho ~11~ hay không?

Input:

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~k~ với ~1 \le n \le 10^{10^6}~ và ~0 \le k \le 10^9~.

Output:

• Một dòng duy nhất chứa chữ YES nếu có thể chia hết, còn ngược lại thì NO.

Sample input 1:

13574 0

Sample output 1:

YES

Sample input 2:

57413 3

Sample output 2:

YES

Sample input 3:

1000 1000

Sample output 3:

NO

Giải thích: trong VD1, ta thấy số ban đầu đã chia hết cho 11 nên dù không được chuyển lần nào (do ~k=0~) nhưng vẫn thỏa mãn, trong VD2, ta thấy ~57413 \to 74135 \to 41357 \to 13574~ thì có số cuối chia hết cho ~11.~ Còn trong VD3 thì cho dù chuyển thế nào cũng không được.

Đã lâu lắm rồi Phú không chơi điện tử. Để chuẩn bị cho tinh thần thoải mái khi bước vào buổi thi lập trình tại vào tuần sau, Phú quyết định bật máy tính lên và tham gia chơi một trò chơi. Trên giao diện bắt đầu của trò chơi có ~n~ xạ thủ được xếp thành một hàng ngang, các xạ thủ được đánh số từ 1 đến ~n~ từ trái sang phải. Phía trước các xạ thủ có một mục tiêu cần phá hủy. Để nhắm vào những vị trí điểm yếu của mục tiêu, Phú bỏ ra ~T~ giây để di chuyển vị trí của các xạ thủ. Tại giây thứ i (~1 \le i \le T~) Phú có thể thực hiện một trong 3 thao tác sau:

• Nháy chuột trái vào xạ thủ thứ ~j~ bất kỳ (~1 \le j \le n~) khi đó xạ thủ thứ ~j~ sẽ bước sang bên trái một bước.
• Nháy chuột phải vào xạ thủ thứ ~k~ bất kỳ (~1 \le k \le n~) khi đó xạ thủ thứ ~k~ sẽ bước sang bên phải một bước.
• Không thực hiện việc gì (để cho tay nghỉ ngơi cho đỡ mỏi).

Biết rằng sau đúng ~T~ giây, vị trí mới của các xạ thủ so với vị trí cũ của họ tạo thành một dãy số nguyên ~A_1,A_2,..,A_n.~ Trong đó ~|A_i | (1 \le i \le n)~ là khoảng cách (tính bằng đơn vị bước) giữa vị trí hiện tại của xạ thủ i so với vị trí ban đầu của xạ thủ i. Chú ý ~A_i~ dương nếu vị trí hiện tại ở bên phải so với vị trí ban đầu, ~A_i~ âm nếu vị trí hiện tại ở bên trái so với vị trí ban đầu. Lưu ý là tại một thời điểm hai xạ thủ khác nhau có thể đứng cùng một vị trí.

Yêu cầu: Hãy cho biết Phú có bao nhiêu cách thực hiện việc di chuyển vị trí của các xạ thủ để được dãy A như trên. Hai cách di chuyển được gọi là khác nhau, nếu như tồn tại ít nhất một giây trong ~T~ giây mà thao tác ở cách di chuyển này khác thao tác ở cách di chuyển kia.

Input: dòng đầu tiên chứa hai số nguyên ~n~ và ~T~ (~1 \le n \le 100;1 \le T \le 1000~). Dòng thứ hai gồm ~n~ số nguyên ~A_1,A_2,..,A_n~ trong đó ~|A_i | \le 1000~ với ~1 \le i \le n.~

Output: một số nguyên duy nhất là số cách di chuyển tìm được. Do số cách có thể rất lớn, bạn hãy lấy kết quả chia dư cho ~10^9+7~. Dữ liệu vào đảm bảo luôn có cách dịch chuyển.

Sample input 1:

2 2

-1 1

Sample output 1:

2

Sample input 2:

2 3

-1 0

Sample output 2:

12

* Giải thích:*

Ở ví dụ 1:

• Cách 1: Giây 1 T(1), giây 2 P(2).
• Cách 2: Giây 1 P(2), giây 2 T(1).

Ở ví dụ 2:

• Cách 1: Giây 1 T(1), giây 2 None, giây 3 None.
• Cách 2: Giây 1 T(1), giây 2 T(2), giây 3 P(2).
• Cách 3: Giây 1 T(1), giây 2 P(2), giây 3 T(2).
• Cách 4: Giây 1 T(1), giây 2 P(1), giây 3 T(1).
• Cách 5: Giây 1 T(1), giây 2 T(1), giây 3 P(1).
• Cách 6: Giây 1 P(1), giây 2 T(1), giây 3 T(1).
• Cách 7: Giây 1 None, giây 2 T(1), giây 3 None.
• Cách 8: Giây 1 None, giây 2 None, giây 3 T(1).
• Cách 9: Giây 1 T(2), giây 2 T(1), giây 3 P(2).
• Cách 10: Giây 1 T(2), giây 2 P(2), giây 3 T(1).
• Cách 11: Giây 1 P(2), giây 2 T(2), giây 3 T(1).
• Cách 12: Giây 1 P(2), giây 2 T(1), giây 3 T(2).

trong đó:

• T(i) - nháy chuột trái vào xạ thủ thứ i;

• P(i) - nháy chuột phải vào xạ thủ thứ i;

• None - không làm gì cả.

Trung là một lập trình viên điện toán đám mây. Hiện tại, anh ấy đang cần phải chạy tổng cộng ~n~ chương trình mô phỏng trên "đám mây". Mỗi chương trình chạy mất đúng 1 đơn vị thời gian, nhưng bộ nhớ chúng sử dụng có thể khác nhau. Bộ nhớ cần thiết cho chương trình ~i~ là ~a_i~ megabyte. Theo công việc, Trung phải chia ~n~ chương trình thành ~k~ tác vụ và số chương trình trong mỗi tác vụ không nhất thiết bằng nhau. Trong mỗi tác vụ, các chương trình được chạy lần lượt, tức là thời gian thực hiện một tác vụ sẽ bằng số chương trình trong tác vụ đó. Mặt khác, bộ nhớ được cấp phát cho mỗi tác vụ bằng bộ nhớ tối đa cần thiết cho bất kỳ một chương trình nào trong tác vụ đó.

Tuy nhiên, Trung phải trả chi phí cho mỗi megabyte trên một đơn vị thời gian, vì vậy chi phí cho mỗi tác vụ bằng số đơn vị thời gian thực hiện tác vụ đó nhân với bộ nhớ tối đa của các chương trình trong tác vụ và bằng số chương trình của tác vụ đó nhân với bộ nhớ tối đa của các chương trình trong tác vụ. Chi phí thực hiện ~n~ chương trình sẽ là tổng chi phí thực hiện ~k~ tác vụ. Bạn hãy giúp Trung chia tác vụ phù hợp sao cho chi phí thực hiện chúng là tối thiểu nhé.

Input: Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1 \le k \le n \le 10^5~). Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~ với ~0 \le a_i \le 10^{12}~.

Output: một số nguyên là chi phí tối thiểu mà Trung phải trả.

Sample input:

10 4

4 1 12 17 7 3 6 8 10 16

Sample output:

94

Trong ví dụ trên, Trung cần chia thành 4 tác vụ như sau:

• Tác vụ 1: Gồm các chương trình thứ nhất, thứ hai và thứ sáu. Chi phí của tác vụ 1 là: ~3 \times \max(a_1,a_2,a_6 )=12;~
• Tác vụ 2: Gồm các chương trình thứ ba và thứ chín. Chi phí của tác vụ 2 là: ~2 \times \max(a_3,a_9 )=24;~
• Tác vụ 3: Gồm các chương trình thứ năm, thứ bảy và thứ tám. Chi phí của tác vụ 3 là: ~3 \times \max(a_5,a_7,a_8 )=24;~
• Tác vụ 4: Gồm các chương trình thứ tư và thứ mười. Chi phí của tác vụ 4 là: ~2 \times \max(a_4,a_{10} )=34.~

Tổng chi phí Trung cần phải trả là: ~12+24+24+34=94.~