Trên mặt phẳng toạ độ người ta vẽ ra ~n~ hình chữ nhật.

Hãy tính diện tích bị che phủ bởi ~n~ hình chữ nhật này, biết rằng ~n~ hình chữ nhật đó đều song song với trục ~OX~ và ~OY~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,q~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.
• ~q~ dòng sau, mỗi dòng gồm ~3~ số nguyên dương ~l,r,x~

Constraints

• ~1 \le n \le 10^5~
• ~1 \le x_i, y_i \le 3\times10^4~

Output

• Gồm một dòng in ra diện tích được phủ bởi ~n~ hình chữ nhật.

Sample Input 1:

2
10 10 20 20
15 15 25 30

Sample Output 1:

225

Explanation 1:

Cho một dãy ~a~ gồm ~n~ phần tử.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~[l,r,x]~, yêu cầu hãy đếm xem có bao nhiêu ~a_i~ với ~i \in [l,r]~ thỏa mãn ~a_i~ là ước hoặc bội của ~x~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,q~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.
• ~q~ dòng sau, mỗi dòng gồm ~3~ số nguyên dương ~l,r,x~

Constraints

• ~1 \le n,q \le 2\times10^5~
• ~1 \le a_i \le 2\times10^5~

Output

• Với mỗi truy vấn, in ra kết quả.

Sample Input 1:

8 5
12 10 3 18 6 72 28 42
1 8 6
3 7 7
2 6 9
1 5 5
4 8 4

Sample Output 1:

6 1 3 1 2 

Công ty Chim có ~n~ thành viên được phân nhiều quyền hạn khác nhau, trong đó người thứ ~1~ là sếp tổng. Mỗi thành viên trừ sếp tổng đều có chính xác một người ~p_i~ là sếp trực tiếp của họ. Người ~u~ được gọi là nằm dưới quyền hạn của người ~v~ nếu như người ~v~ là sếp trực tiếp của người ~u~, hoặc sếp trực tiếp của người ~u~ nằm dưới quyền hạn của người ~v~. Hay nói cách khác, cách phân quyền hạn của công ty Chim có cấu trúc như một đồ thị dạng cây.

Công ty đang có ~m~ phương án tăng lương cho các thành viên. Ở phương án thứ ~i~, công ty sẽ tăng lương cho người thứ ~u_i~ và tất cả các thành viên nằm dưới quyền hạn của người thứ ~u_i~ lên ~w_i~ đồng. Để đánh giá được độ thích hợp của những phương án này, công ty đặt ra ~q~ khảo sát. Ở khảo sát thứ ~i~, công ty muốn kiểm tra rằng nếu như chỉ có những phương án thứ ~t~ ~\forall t \in [L_i, R_i]~ được thực thi, người thứ ~u_i~ được tăng lương tổng cộng bao nhiêu đồng. Bạn hãy giúp công ty tìm ra câu trả lời cho ~q~ khảo sát này nhé.

Input

• Dòng đầu chứa ba số nguyên dương ~n, m, q~ ~(1 \le n, m, q \le 10^5)~.
• Dòng thứ hai chứa ~n - 1~ số nguyên dương ~p_2, p_3, \ldots, p_n~ ~(1 \le p_i \le n)~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~u_i, w_i~ ~(1 \le u_i \le n, \ 1 \le w_i \le 10^9)~.
• ~q~ dòng cuối cùng, dòng thứ ~i~ chứa ba số nguyên dương ~L_i, R_i, u_i~ ~(1 \le L_i \le R_i \le m, \ 1 \le u_i \le n)~.

Dữ liệu bảo đảm cấu trúc phân quyền của công ty là một đồ thị dạng cây.

Output

• In ra ~q~ dòng, dòng thứ ~i~ chứa câu trả lời cho khảo sát thứ ~i~.

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~n, m, q \le 500~
• Subtask ~2~ (~20\%~ số điểm): ~L_i = 1, R_i = m \ \forall i \in [1, q]~
• Subtask ~3~ (~20\%~ số điểm): ~n, m, q \le 5000~
• Subtask ~4~ (~20\%~ số điểm): ~p_i = i - 1 \ \forall i \in [2, n]~
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

6 6 4
1 5 5 2 5 
6 9
4 10
1 6
5 5
5 6
6 5
2 5 5
1 1 1
2 3 2
1 4 1

Sample output 1

17
0
6
6

Xét một xâu có chiều dài ~n~ bao gồm các chữ số ~0~ hoặc ~1~. Điểm của xâu được tính như sau:

• Với mỗi số nguyên ~i~ ~(1 \le i \le m)~, tổng điểm của xâu sẽ được tăng thêm ~a_i~ nếu như xâu con bao gồm các kí tự từ ~l_i~ đến ~r_i~ (kể cả biên) có ít nhất một kí tự ~1~.

Với mọi xâu độ dài ~n~, số điểm cao nhất có thể đạt được là bao nhiêu.

Input

• Dòng đầu tiên gồm hai số nguyên ~n,m~
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~l_i,r_i,a_i~.

Constraints

• ~1 \le n,m \le 2*10^5~
• ~1 \le l_i,r_i \le n, |a_i| \le 10^9~

Subtask :

• Subtask 1: ~n \le 5000~ ~(50\%)~
• Subtask 2: ~n \le 5*10^5~ ~(50\%)~

Output

• In ra số điểm lớn nhất có thể.

Sample Input 1:

5 3
1 3 10
2 4 -10
3 5 10

Sample Output 1:

20

Explanation 2:

• Xâu 10001 là xâu tối ưu.

Sample Input 2:

3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30

Sample Output 2:

90

Explanation 2:

• Xâu 100 là xâu tối ưu.

Sample Input 3:

6 8
5 5 3
1 1 10
1 6 -8
3 6 5
3 4 9
5 5 -2
1 3 -6
4 6 -7

Sample Output 3:

10

Explanation 3:

• Xâu 101000 là xâu tối ưu.

Là sinh viên ngành Công nghệ thông tin, Nam thường xuyên rèn luyện tư duy và kĩ năng lập trình bằng các bài toán lập trình thi đấu. Một bài toán thú vị mà Nam đang suy nghĩ để giải như sau:

Cho ~n~ đoạn số nguyên trên trục số, đoạn thứ ~k~ ~(1 \le k \le n)~ có đầu mút bên trái là ~L_k~, đầu mút bên phải là ~R_k~ và có trọng số là ~w_k~. Với ~a,b~ là hai số nguyên, trọng số của ~(a,b)~ được tính bằng tổng trọng số của tất cả các đoạn ~t~ mà ~a \le L_t \le R_t \le b~ với ~1 \le t \le n~. Cần tìm số nguyên ~(a,b)~ có trọng số lớn nhất.

Yêu Cầu: Cho ~n~ đoạn số, gọi ~S~ là trọng số của cặp số nguyên ~(a,b)~ có trọng số là lớn nhất, hãy giúp Nam xác định giá trị ~S~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~.
• Dòng thứ ~k~ ~(1 \le k \le n)~ trong ~n~ dòng tiếp theo chứa ba số nguyên ~L_k,R_k,w_k~ mô tả đoạn thứ ~k~ ~(1 \le L_k \le R_k \le 10^6; |w_k| \le 10^6)~

Subtask

• Có ~30\%~ số test có: ~n \le 200~.
• Có ~30\%~ số test có: ~n \le 2000~.
• Có ~20\%~ số test có: ~R_1 - L_1 = R_2 - L_2 = ... = R_n - L_n~ và ~n \le 10^5~.
• Có ~20\%~ số test có: ~n \le 10^5~.

Output

• Gồm một số nguyên ~S~ là trọng số lớn nhất tìm được.

Sample Input 1:

4
1 2 -5
3 5 6
3 4 -1
4 6 3

Sample Output 1:

8

Explanation 1:

Trọng số lớn nhất là ~8~ bằng cách chọn cặp số ~(3,6)~.

Trọng số của cặp số ~(3,6)~ bằng tổng trọng số của ba đoạn: ~[3,5],[3,4]~ và ~[4,6]~.

Đối với một dãy ~b_1,b_2,...,b_m~, một vị trí ~1 \le i < m~ được gọi là "cutable" nếu như tất cả các phần tử trong đoạn ~[b_1,b_2,...,b_i]~ đều bé hơn các phần tử trong đoạn ~[b_{i+1},...,b_m]~.

Cho dãy nguyên dương ~a_1,a_2,...,a_n~ gồm các số nguyên phân biệt trong đoạn ~[1,n]~. Bạn cần trả lời ~q~ truy vấn, mỗi truy vấn gồm hai số nguyên dương ~l,r~. Hãy đếm số vị trí "cutable" đối với dãy ~a_l,a_{l+1},...,a_r~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ miêu tả hoán vị ~a~.
• Dòng thứ ba chứa số nguyên dương ~q~.
• ~q~ dòng sau, mỗi dòng gồm hai số nguyên dương ~l,r~ ~(1 \le l < r \le n)~ miêu tả truy vấn.

Output

• Với mỗi truy vấn, in ra kết quả tương ứng.

Constraints .

• ~1 \le n,q \le 2*10^5~

Subtask

• Sub ~1~ (~50\%~): ~n,q \le 1000~.
• Sub ~2~ (~50\%~): ~n,q \le 3 \times 10^5~.

Sample Input 1

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

Sample Output 1

1
1
2
0

Trên dãy số nguyên ~a_1,a_2,...,a_n~ và với hai số nguyên ~w_1,w_2~, ta định nghĩa một bộ năm chỉ số ~1 \le i_1 < i_2 < ... < i_5 \le n~ được gọi là bộ năm và có trọng số được tính bằng: ~(w_1 \times a_{i_1}) + (w_2 \times a_{i_2}) + a_3 + (w_2 \times a_{i_4}) + (w_1 \times a_{i_5})~.

Ví dụ, trên dãy gồm ~7~ số nguyên ~2,8,1,9,1,-1,8~ và ~w_1 = 1~, ~w_2 = -1~ thì bộ năm chỉ số ~2,3,4,6,7~ là một bộ năm có trọng số bằng ~(1 \times 8) + (-1 \times 1) + 9 + (-1 \times (-1)) + (1 \times 8) =25~, đây cũng là bộ năm có trọng số lớn nhất trong tất cả các bộ năm.

Yêu cầu: Cho dãy số ~a_1,a_2,...,a_n~ và hai số nguyên ~w_1~ và ~w_2~. Hãy tìm bộ năm có trọng số lớn nhất.

Input

• Dòng đầu chứa ba số nguyên ~n,w_1,w_2~ ~(5 \le n \le 10^5; |w_1|, |w_2| \le 100)~
• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...,a_n~ ~(|a_i| \le 10^9)~.

Output

• Gồm một số nguyên là trọng số của bộ năm lớn nhất tìm được.

Subtask

• Có ~20\%~ số test ứng với ~1 \le n \le 100~
• Có ~20\%~ số test ứng với ~w_1 = w_2 = 0~
• Có ~20\%~ số test ứng với ~n \le 5000, w_1 = 0~
• Có ~20\%~ số test ứng với ~w_1 = 0~
• Có ~20\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

7 1 -1
2 8 1 9 1 -1 8

Sample Output 1

25

Sample Input 2

7 0 0
2 8 1 9 1 -1 8

Sample Output 2

9

Hè đã tới, ~mrtee~ muốn cho các học sinh của mình vận động một chút. Thầy đã lập ra một cuộc thi nhảy xa, tuy nhiên điều luật của nó thì rất lạ.

Nếu chiếu trên trục ~OX~, đường nhảy sẽ bắt đầu từ điểm ~1~ và kết thúc tại điểm ~n~. Bạn sẽ xuất phát từ điểm ~0~ và được nhảy bao nhiêu lượt tùy thích, miễn là không ra khỏi phạm vi ~[1,n]~. Tuy nhiên, mỗi lượt bạn phải nhảy một quãng đường nguyên dương và ở lần nhảy thứ ~i~, bạn phải nhảy một quãng đường có độ chia hết cho ~k+i-1~. Tất nhiên, bạn sẽ được cung cấp trước ~2~ giá trị ~n~ và ~k~.

Là một ~coder~ yêu thích toán học, bạn không quan tâm tới việc thắng thua trong cuộc thi này lắm, mà chỉ hứng thú với việc đếm xem với mỗi vị trí ~i~ thuộc đoạn ~[1,n]~, có bao nhiêu cách nhảy khác nhau từ điểm xuất phát tới đó.

Hãy thử lập trình và giải đáp câu hỏi ấy!

Input

• Gồm một dòng chứa hai số nguyên dương ~n, k~.
  
  

Output

• In ra ~n~ số nguyên, số thứ ~i~ là số cách để nhảy từ điểm ~0~ tới điểm ~i~, vì kết quả có thể rất lớn nên hãy lấy phần dư với modulo ~10^9+7~.
  
  

Constraints

• ~1 \le k \le n \le 2*10^5~
  
  

Subtasks

• ~35\%~ số điểm: ~n \le 300~.
• ~40\%~ số điểm: ~n \le 4000~.
• ~25\%~ số điểm: ~n \le 2*10^5~.
  
  

Sample Test 1

Input:

12 1

Output:

1 1 2 2 3 4 5 6 8 10 12 15

Sample Test 2

Input:

15 3

Output:

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

Giải thích

• Ở ví dụ ~1~, các cách để đến điểm ~6~ là ~[0,6],[0,4,6],[0,2,6],[0,1,3,6]~.
• Ở ví dụ ~2~, các cách để đến điểm ~15~ là ~[0,15],[0,3,12],[0,6,10,15]~

Vào năm ~3202~, trò chơi "Fake Pyramid" đang vô cùng thịnh hành với giới trẻ.

Trong trò chơi này, bạn được nhận một mảnh giấy kẻ ~n~ dòng và ~m~ cột, tạo ra ~n \times m~ ô vuông. Ô ở hàng ~i~ và cột ~j~ được gọi là ô ~(i,j)~. Mỗi ô ~(i,j)~ đều có một giá trị là ~a_{i,j}~, nếu ~a_{i,j} = 0~ thì nghĩa là ô đó đã bị "cấm", ngược lại, ~a_{i,j}~ sẽ mang một giá trị nguyên dương.

Bạn cần tìm cách vẽ ra một kim tự tháp trên mảnh giấy được cho theo luật như sau (do vẽ trên giấy nên có thể sẽ khác so với tưởng tượng):

• Đầu tiên, bạn chọn ra hai giá trị ~A,B~ thỏa mãn ~1 \le A \le B \le n~.
• Với mỗi ~i~ thuộc đoạn ~[A,B]~, bạn chọn ra hai giá trị ~L_i,R_i~ thỏa mãn ~1 \le L_i \le R_i \le m~. Bạn cần chọn các giá trị ~L_i,R_i~ này sao cho với mọi ~i \in [A,B-1]~, ~L_i \ge L_{i+1}~ và ~R_i \le R_{i+1}~
• Sau khi chọn xong các giá trị, bạn sẽ thu được một kim tự tháp được tạo bởi các ô ~(i,j)~ thỏa mãn ~i \in [A,B]~ và ~j \in [L_i,R_i]~.
• Nói cách khác, với mỗi hàng từ ~A~ tới ~B~, bạn sẽ cần chọn ra một số ô liên tiếp sao cho các ô ở hàng dưới trùm lên các ô ở hàng trên.
• Để tăng độ khó cho trò chơi, kim tự tháp của bạn vẽ ra không được chứa ô nào bị cấm.
• Giá trị của một kim tự tháp chính là tổng giá trị các ô nó chứa.

Ví dụ, cho mảnh giấy ~5 \times 5~ có minh họa như sau:

Ta chọn:

• ~A = 1; B = 3~.
• ~L_1 = 1; R_1 = 1~.
• ~L_2 = 1; R_2 = 3~.
• ~L_3 = 1; R_3 = 3~.

Sẽ thu được kim tự tháp thỏa mãn ở dưới (những ô màu cam là những ô nằm trong kim tự tháp):

Dưới đây cũng là một kim tự tháp thỏa mãn:

Tuy nhiên, hình ảnh dưới đây lại không phải một kim tự tháp thỏa mãn do chứa ô có giá trị ~a(i,j) = 0~ (ô bị cấm):

Cuối cùng, ta có minh họa dưới đây cũng không phải một kim tự tháp do ~L_4 < L_5~

MoHuymed Salah rất hứng thú với trò chơi này, nhưng do anh đang bận rộn với định lý một mùa dài ~7~ năm của mình nên dù đã có một mảnh giấy nhưng chưa có thời gian để tìm ra lời giải tối ưu nhất. Bạn hãy giúp anh ấy nhé.

Yêu cầu: Cho ma trận ~n \times m~ miêu tả mảnh giấy, hãy tìm cách vẽ kim tự tháp sao cho thu được tổng lớn nhất có thể.

Dữ liệu vào từ tệp văn bản: kimtuthap.inp

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(1 \le n,m \le 2000)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~m~ số nguyên dương ~a_{i,1}, a_{i,2}, ..., a_{i,m}~ miêu tả mảng giá trị ~a~ ~(a_{i,j} \le 50)~.
• Dữ liệu đảm bảo luôn luôn tồn tại ít nhất một giá trị ~a(i,j) \neq 0~.

Kết quả ghi ra tệp văn bản: kimtuthap.out

• In ra một số nguyên là giá trị lớn nhất có thể đạt được của một kim tự tháp.

Ràng buộc

• Có ~15\%~ số test thỏa mãn: ~n = 1~.
• Có ~20\%~ số test thỏa mãn: Nếu hàng ~i~ ~(1 \le i \le n)~ có ô bị cấm, thì tất cả các ô trong hàng đó cũng đều bị cấm.
• Có ~20\%~ số test thỏa mãn: ~n,m \le 60~.
• Có ~25\%~ số test thỏa mãn: ~n,m \le 300~.
• ~20\%~ số test còn lại không có ràng buộc gì thêm.

Ví dụ

Input 1

5 5
5 0 1 4 4
7 12 6 5 4
5 7 8 0 1
1 6 4 5 0
1 0 7 5 8

Output 1

66

Input 2

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

Output 2

15

Giải thích

Ở ví dụ ~1~, ta lấy kim tự tháp theo hình dưới đây:

Còn đây là kim tự tháp ta cần lấy ở ví dụ ~2~:

Các nghiện thủ đang bị nhốt trong căn phòng có 1 mật mã được mã hóa trong mảng ~A~ có độ dài ~n~. Bởi muốn nghiện Liên Quân, thần đồng đã sai người tìm và giải mã nó. Ta biết được mảng ~A~ có thể chia thành nhiều dãy con liên tiếp (và có ~2^{n-1}~ cách chia ). Với mỗi dãy con được chia, giá trị của dãy con đấy nếu gồm các số từ vị trí ~l~ đến ~r~ là :

• ~r \;– \; l + 1 ~ nếu tổng các số từ ~l~ đến ~r~ lớn hơn hẳn 0.
• 0 nếu tổng các số từ ~l~ đến ~r~ bằng 0.
• ~–(r \;– \; l + 1)~ nếu tổng các số từ ~l~ đến ~r~ nhỏ hơn hẳn 0.

Gọi ~S~ là tổng các giá trị của dãy con trong 1 cách chia. Mã hóa của căn phòng là ~S~ lớn nhất trong tất cả các cách chia. Biết rằng tin Ams 21-24 toàn những feeder liên quân và best tin học, thần đồng muốn nhờ các bạn tìm mật mã trên.

Input

• Dòng đầu tiên gồm số ~n~
• Dòng tiếp theo gồm ~n~ số của mảng ~A~

Output

• In ra một số là giá trị ~S~ lớn nhất tìm được.

Sample Test

Input:

5
-1 -2 3 -1 -1

Output

1

Sample Test 2

Input:

6
-1 2 -3 4 -5 6

Output

6

Sample Test 3

7
1 -1 -1 1 -1 -1 1

Output

-1

Giải thích:

• Test 1 chia thành (-1 -2 ) (3 -1 -1)
• Test 2 chia thành (-1 2 -3 4 -5 6)
• Test 3 chia thành (1 -1 -1 1 -1) (-1 1)

Ràng buộc:

• ~A_i \le 10^9~
• Subtask 1: ~n \le 20~ (30%)
• Subtask 2: ~n \le 5000~ (40%)
• Subtask 3: ~n \le 5*10^5~ (30%)

Cho hai số nguyên dương ~n~ và ~k~.

Ta có thể xây dựng một dãy số nguyên dương ~a~ gồm ~n~ phần tử: ~a_1,a_2,...,a_n~ sao cho với mọi ~1 \le i \le n~ thỏa mãn điều kiện ~a_i \in [1,k]~.

Gọi ~g(a)~ là ước chung lớn nhất của dãy số ~a~.

Nhiệm vụ của bạn chính là tính tổng ~g(a)~ của mọi dãy số có thể xây dựng (có ~k^n~ dãy số như vậy).

Vì kết quả có thể rất lớn, hãy in nó ra theo module ~10^9+7~.

Input: nhập vào từ file "SUMGCD.INP"

• Gồm một dòng chứa hai số nguyên dương ~n,k~ ~(1 \le n \le 10^9, 1 \le k \le 10^6)~.

Output: ghi ra file "SUMGCD.OUT"

• In ra kết quả theo module ~10^9+7~.

Subtask

• Subtask ~1~ ~(20\%)~: ~n,k \le 7~
• Subtask ~2~ ~(20\%)~: ~n \le 10^5, k = 4~
• Subtask ~3~ ~(25\%)~: ~n \le 10^5, k \le 20~
• Subtask ~4~ ~(20\%)~: ~k \le 10^5~
• Subtask ~5~ ~(15\%)~: Không giới hạn gì thêm.

Ví dụ

Sample Input 1

1  5

Sample Output 1

15

Sample Input 2

5 4

Sample Output 2

1060

Sample Input 3

3 2

Sample Output 3

9

Giải thích

Ở ví dụ ~3~ ta có:

• ~g([1,1,1]) = 1~
• ~g([1,1,2]) = 1~
• ~g([1,2,1]) = 1~
• ~g([1,2,2]) = 1~
• ~g([2,1,1]) = 1~
• ~g([2,1,2]) = 1~
• ~g([2,2,1]) = 1~
• ~g([2,2,2]) = 2~

Kết quả thu được là ~9~.

Tỉ phú Vương dự định sẽ xây một thủy cung thu hút khách du lịch. Để thực hiện dự định đó, ông ta đã mua ~n~ chú cá và ~m~ bể thủy sinh. Chú cá thứ ~i~ có sức mạnh là ~a_i~

Vương cần phải quyết định xem, với mỗi chú cá thì ông sẽ đặt vào bể thủy sinh nào. Tuy nhiên, việc này không hề đơn giản, khi ông sẽ phải xem xét đến giới hạn không gian và khả năng kìm hãm sự phát triển lẫn nhau giữa những chú cá trong cùng một bể. Sau những tính toán kĩ lưỡng, ông đã ước tính rằng mức độ bất ổn của mỗi chú cá sẽ bằng tổng sức mạnh của các chú cá nằm cùng bể thủy sinh với chú cá đó (bao gồm cả bản thân chú cá đó).

Yêu cầu: Hãy giúp tỉ phú Vương đặt các chú cá vào các bể thủy sinh sao cho tổng độ bất ổn của các chú cá là nhỏ nhất.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ ~(1 \le m \le n \le 2000)~ cho biết số chú cá và số bể thủy sinh.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, . . . , a_n (1 \le ai \le 10^9 )~ cho biết sức mạnh của các chú cá.

Output

• In một số nguyên duy nhất là tổng độ bất ổn nhỏ nhất của các chú cá.

Subtask

• Có ~20\%~ số test ứng với ~n \le 8~.
• Có ~20\%~ số test khác ứng với ~n \le 15~.
• Có ~20\%~ số test khác ứng với ~m = 2~.
• Có ~30\%~ số test khác ứng với ~n \le 100~.
• ~10\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

6 3
9 2 11 3 5 8

Sample Output 1

75

Sample Input 2

4 4
10 20 30 40

Sample Output 2

100

Explanation

Trong ví dụ thứ nhất, một cách đặt cá vào bể thủy sinh tối ưu như sau:

• Đặt chú cá thứ ~1, 6~ vào bể thứ nhất.
• Đặt chú cá thứ ~2, 4, 5~ vào bể thứ hai.
• Đặt riêng chú cá thứ ~3~ vào bể thứ ba. Độ bất ổn của các chú cá lần lượt là ~17 + 10 + 11 + 10 + 10 + 17 = 75~.

Ở ví dụ thứ hai, ta sẽ đặt riêng mỗi chú cá vào một bể thủy sinh.

Bạn được tham gia trò chơi với dãy gồm ~n~ số nguyên không âm. Trong trò chơi này bạn phải chia dãy đã cho ra thành ~k+1~ đoạn khác rỗng. Để thu được ~k+1~ đoạn bạn cần lặp lại các bước sau đây ~k~ lần:

~1~. Chọn một đoạn tuỳ ý với nhiều hơn một phần tử (đầu tiên bạn chỉ có một đoạn - đó chính là dãy ban đầu).

~2~. Chọn một vị trí nào đó giữa hai phần tử của đoạn đã chọn để chia nó ra làm hai đoạn mới khác rỗng.

Mỗi lần thực hiện xong hai bước này bạn nhận được một điểm số bằng tích của hai tổng các số trong hai đoạn mới chia ra.

Yêu cầu: Với cách chơi như trên, bạn hãy tìm cách chơi để đạt được tổng điểm lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ ~(k+1 \le n \le 3000)~

• Dòng thứ hai chứa n số nguyên không âm ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 10^4 , 1 \le i \le n)~ là các phần tử của dãy số.

Output

Một số nguyên duy nhất là tổng điểm lớn nhất mà bạn đạt được.

Sample Input

7 3
1 3 4 0 2 3 4

Sample Output

108

Giải thích

Trong ví dụ bạn có thể giành được 108 điểm theo cách sau:

• Đầu tiên bạn có dãy số (1, 3, 4, 0, 2, 3, 4) gồm 1 đoạn. Bạn chia dãy ra thành hai đoạn sử dụng điểm chia sau phần tử thứ sáu và nhận được: (1 + 3 + 4 + 0 + 2 + 3) × 4 = 52 điểm.

• Bạn đang có hai đoạn (1, 3, 4, 0, 2, 3), (4). Bạn chia dãy sau phần tử thứ hai và nhận được: (1 + 3) × (4 + 0 + 2 + 3) = 36 điểm.

• Bạn đang có ba đoạn (1, 3), (4, 0, 2, 3), (4). Bạn chia dãy sau phần tử thứ tư và nhận được: (4 + 0) × (2 + 3) = 20 điểm.

Như vậy, sau 3 bước thực hiện nói trên bạn chia dãy số thành 4 đoạn (1, 3), (4, 0), (2, 3), (4) và nhận được: 52 + 36 + 20 = 108 điểm.

Subtask

• Có 70% số test tương ứng với 70% số điểm của bài có n ≤ 300;
• Có 30% số test còn lại tương ứng với 30% số điểm của bài có n ≤ 3000.