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 đặ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, \dots, a_n~ (~1 \le a_i \le 10^9~) cho biết sức mạnh của các chú cá.

Output

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

Sample Input 1

6 3
9 2 11 3 5 8

Sample Output 1

75

Khi luyện tập sang dạng bài xử lý xâu cho kì thi học sinh giỏi quốc gia sắp tới, Tuấn gặp một bài toán thú vị như sau:

Cho một xâu ~S = S_1S_2 \dots S_n~ gồm ~n~ kí tự latin viết thường và một số nguyên không âm ~d~, các kí tự của ~S~ được đánh số từ 1 đến ~n~ từ trái qua phải.

Tiếp theo cho một số nguyên ~k~ (~1 \le k \le n~) và tạo ra ~m = \lfloor \frac{n}{k} \rfloor~ xâu độ dài ~k~, xâu thứ ~i~ trong ~m~ xâu là một xâu các kí tự con liên tiếp độ dài ~k~ của ~S~ bắt đầu từ vị trí ~(i - 1) \times k + 1~. Nhắc lại, ~[z]~ là phép toán lấy phần nguyên của số ~z~. Nói một cách khác thì xâu ~S~ được cắt thành ~m~ xâu độ dài ~k~ và bỏ đi phần thừa. Kí hiệu xâu thứ ~i~ trong ~m~ xâu vừa được cắt là ~P^i~, khi đó ~P^i = S_{(i-1) \times k + 1} S_{(i-1) \times k + 2} \dots S_{i \times k}~.

Định nghĩa ~dist(X, Y)~ là khoảng cách Hamming của hai xâu ~X~ và ~Y~ có cùng độ dài ~k~, nghĩa là số vị trí ~u~ (~1 \le u \le k~) mà kí tự thứ ~u~ của ~X~ khác kí tự thứ ~u~ của ~Y~. Gọi ~f(k) = |\{(i, j) | (1 \le i < j \le m) \text{ thoả mãn } dist(P^i, P^j) \le d\}|~. Nói một cách khác, ~f(k)~ là số cặp xâu trong các xâu ~P~ thỏa mãn hai xâu đó khác nhau ở nhiều nhất ~d~ vị trí.

Yêu cầu: Với mỗi giá trị ~k~ từ 1 đến ~n~, hãy tính giá trị ~f(k)~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ (~1 \le n \le 5 \times 10^4~) và ~d~ (~0 \le d \le 1~);
• Dòng thứ hai chứa xâu ~s~ độ dài ~n~, gồm ~n~ kí tự latin viết thường.

Output

• Ghi ra ~n~ số nguyên trên một dòng, số nguyên thứ ~k~ là giá trị của ~f(k)~.

Sample Input 1

11 0
ababaaabaaa

Sample Output 1

31 4 1 0 0 0 0 0 0 0 0

Cô Thái rất thích sự tròn trĩnh của những chữ số 0. Là giáo viên chuyên tin, cô Thái cho các bạn học sinh giỏi làm bài tập đếm số lượng hình chữ nhật chỉ chứa toàn số 0 trong một bảng hình chữ nhật. Cụ thể, cho một bảng hình chữ nhật kích thước ~n \times n~ ô, mỗi ô chỉ chứa số 0 hoặc 1. Các hàng đánh số từ 1 đến ~n~ từ trên xuống dưới, các cột đánh số từ 1 đến ~n~ từ trái qua phải. Có ~q~ truy vấn, mỗi truy vấn sẽ thay đổi giá trị của một ô từ 0 thành 1 hoặc từ 1 thành 0.

Yêu cầu: Với mỗi truy vấn, sau khi thay đổi giá trị hãy đếm số hình chữ nhật con (tính cả hình chữ nhật ban đầu) có cạnh song song với cạnh của bảng mà chỉ chứa các số 0.

Input

• Dòng đầu chứa hai số nguyên ~n, q~ (~1 \le n, q \le 5000~).
• Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa một xâu 01 độ dài ~n~ mô tả hàng thứ ~i~ của bảng ban đầu.
• Dòng thứ ~i~ trong số ~q~ dòng tiếp theo chứa hai số nguyên ~r, c~ (~1 \le r, c \le n~) mô tả toạ độ ô thay đổi giá trị trong truy vấn thứ ~i~.

Output

• Ghi ra ~q + 1~ dòng trong đó:
• Dòng đầu là số lượng hình chữ nhật con thỏa mãn của bảng ban đầu;
• Mỗi dòng trong số ~q~ dòng tiếp theo ghi một số nguyên là kết quả của truy vấn tương ứng.

Sample Input 1

4 3
0001
0100
1000
0010
2 3
2 2
3 1

Sample Output 1

29
23
31
45

Tuấn có một bộ bài gồm ~n~ quân bài được trải ra thành một dãy từ trái sang phải, trên mỗi quân bài ghi một số nguyên là giá trị của quân bài đó. Gọi giá trị của ~n~ quân bài lần lượt theo dãy trải ra là ~A_1, A_2, \dots, A_n~. Tuấn đưa ra các định nghĩa như sau:

• Một đoạn con là một chuỗi các quân bài liên tiếp nhau trong dãy ~n~ quân bài ban đầu;
• Trọng số của một đoạn con là tổng các giá trị của các quân bài trong đoạn;
• Độ cân bằng của bộ bài là trọng số của đoạn con có trọng số lớn nhất trong dãy ~n~ quân bài.

Tuấn rủ Tú đến nhà chơi bài và yêu cầu Tú tính độ cân bằng của bộ bài theo định nghĩa trên. Sau khi Tú tính xong Tuấn tiếp tục đố Tú chỉnh sửa một số giá trị quân bài để bộ bài đạt độ cân bằng cao nhất với các nguyên tắc chỉnh sửa như sau:

• Đầu tiên, Tuấn đưa cho Tú một dãy ~n~ số nguyên ~B_1, B_2, \dots, B_n~;
• Có tối đa ~k~ lượt chỉnh sửa, mỗi lượt Tú được phép chọn một đoạn con các phần tử từ vị trí thứ ~l~ đến vị trí thứ ~r~ (~1 \le l \le r \le n~) và thực hiện phép gán ~A_i = A_i \times B_i~ với mọi ~i \in [l, r]~.

Hãy giúp Tú đưa ra được độ cân bằng lớn nhất với tối đa ~k~ lượt chỉnh sửa.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1 \le n \le 10^5~; ~0 \le k \le 10~).
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~ (~|A_i| \le 1000~).
• Dòng thứ ba chứa ~n~ số nguyên ~B_1, B_2, \dots, B_n~ (~|B_i| \le 10~).

Output

• Ghi ra một số nguyên duy nhất là độ cân bằng lớn nhất tìm được của bộ bài sau khi sử dụng tối đa ~k~ lượt chỉnh sửa.

Sample Input 1

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

Sample Output 1

13

Sample Input 2

3 0
-4 -10 -8
2 2 -1

Sample Output 2

-4

Hoành Sơn là một địa điểm du lịch nổi tiếng trên toàn thế giới bởi sự hùng vĩ cũng như sự đa dạng phong phú về các dãy núi và những cây cầu bắc qua. Địa điểm du lịch Hoành Sơn có các dịch vụ tham quan theo yêu cầu. Cụ thể là bạn chỉ việc đưa ra yêu cầu của lộ trình, sau đó dịch vụ sẽ tính toán và đưa bạn đi qua các cây cầu và ngọn núi theo đúng yêu cầu về lộ trình.

Địa điểm du lịch ở đây có ~N~ ngọn núi và ~M~ cây cầu, mỗi cây cầu nối hai ngọn núi nào đó với nhau. Giữa hai ngọn núi bất kì có thể có nhiều cây cầu nối hai ngọn núi đó với nhau. Cũng có thể có những ngọn núi có những cây cầu tự nối với chính nó tạo ra hình vòng cung để những khách du lịch có thể đứng xung quanh ngọn núi tham quan và chụp ảnh. Hiểu đơn giản thì mô hình của khu du lịch là một đa đồ thị vô hướng ~N~ đỉnh ~M~ cạnh.

Các ngọn núi được đánh số từ ~1~ đến ~N~ và ngọn núi thứ ~i~ có độ cao là ~A_i~. Về độ dốc của các cây cầu thì nó được tính theo chênh lệch chiều cao của hai ngọn núi ở hai đầu cây cầu. Nói cách khác, nếu cây cầu nối hai ngọn núi ~x~ và ~y~ thì độ dốc của nó là ~|A_x - A_y|~.

Sau khi đạt giải quốc gia, Tuấn muốn tự thưởng cho mình chuyến du lịch đến Hoành Sơn sau cả năm trời ôn luyện vất vả và chuẩn bị bước vào đại học. Đến Hoành Sơn, Tuấn muốn thiết kế một hành trình “lên đỉnh siêu dốc", xuất phát từ một ngọn núi nào đó, đi đến các ngọn núi khác với điều kiện ngọn núi sau cao hơn ngọn núi trước, không những thế, độ dốc của cây cầu sau cũng phải lớn hơn độ dốc của cây cầu trước đó. Nghĩa là, nếu như Tuấn quyết định chọn một hành trình đi qua các ngọn núi theo thứ tự ~P_1, P_2, \dots, P_k~ thì hành trình đó sẽ phải thỏa mãn tính chất: ~0 < A_{P_2} - A_{P_1} < A_{P_3} - A_{P_2} < \dots < A_{P_k} - A_{P_{k-1}}~

Hãy giúp hướng dẫn viên du lịch tìm cho Tuấn hành trình “lên đỉnh siêu dốc” qua nhiều đỉnh núi nhất và trả lời thắc mắc của Tuấn là có bao nhiêu hành trình khác nhau đạt được nhiều đỉnh núi nhất như vậy. Hai hành trình gọi là khác nhau nếu như tồn tại một cây cầu của hành trình này không có trong hành trình kia hoặc ngược lại.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~M~ (~1 \le N \le 3 \times 10^5~, ~1 \le M \le 5 \times 10^5~).
• Dòng thứ hai chứa độ cao của ~N~ ngọn núi là ~N~ số nguyên dương ~A_1, A_2, \dots, A_n~ (~1 \le A_i \le 10^9~).
• Dòng thứ ~i~ trong số ~M~ dòng tiếp theo chứa cặp số nguyên dương ~(U_i, V_i)~ là chỉ số hai ngọn núi là hai đầu của cây cầu thứ ~i~ (~1 \le U_i, V_i \le N~).

Output

• Dòng đầu tiên ghi ra một số nguyên là số lượng đỉnh núi của hành trình tìm được.
• Dòng thứ hai ghi ra một số nguyên là phần dư trong phép chia số lượng lộ trình khác nhau tìm được cho ~10^9 + 7~.

Sample Input 1

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

Sample Output 1

3
1

Để mở đầu cho kỉ nguyên chinh phục vũ trụ, các nhà khoa học ở hành tinh Alpha đang tiến hành thiết kế một chiếc tàu vũ trụ. Trong đó, bộ phận quan trọng nhất là hệ thống động cơ của tàu.

Các nhà khoa học đã mô hình hóa vũ trụ thành hệ trục tọa độ Oxy trong không gian hai chiều, lấy hành tinh Alpha làm gốc tọa độ. Có ~n~ vị trí có thể lắp ráp động cơ trên tàu vũ trụ. Việc lắp ráp động cơ ở vị trí thứ ~i~ tốn chi phí là ~w_i~, và sẽ cho phép tàu di chuyển theo hướng ~(a_i, b_i)~. Cụ thể, giả sử tàu đang nằm ở tọa độ ~(x, y)~ thì khi sử dụng động cơ thứ ~i~ trong khoảng thời gian ~t~ (~t~ là số thực không âm, có thể lớn tùy ý) tàu sẽ đi đến vị trí ~(x + a_i \times t, y + b_i \times t)~.

Một trong những tiêu chí quan trọng nhất trong thiết kế hệ thống tên lửa là tàu phải đi đến được mọi địa điểm trong vũ trụ, tức là với mọi điểm ~(x, y)~, tàu luôn có thể xuất phát từ gốc tọa độ và đi đến điểm ~(x, y)~ chỉ bằng các động cơ được lắp ráp. Nói cách khác, giả sử tàu được lắp ráp động cơ ở các vị trí ~r_1, r_2, \dots, r_k~ thì cần đảm bảo rằng, với mọi điểm ~(x, y)~ luôn tồn tại một bộ số thực ~t_1, t_2, \dots, t_k~ không âm sao cho ~a_{r_1} \times t_1 + a_{r_2} \times t_2 + \dots + a_{r_k} \times t_k = x~ và ~b_{r_1} \times t_1 + b_{r_2} \times t_2 + \dots + b_{r_k} \times t_k = y~.

Hãy giúp các nhà khoa học hành tinh Alpha chọn ra các vị trí cần lắp ráp động cơ sao cho tàu có thể đi đến được mọi điểm trong vũ trụ, và tổng chi phí lắp ráp động cơ là nhỏ nhất.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ (~1 \le n \le 2 \times 10^5~) cho biết số vị trí có thể lắp động cơ.
• Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa ba số nguyên ~a_i, b_i, w_i~ (~|a_i|, |b_i| \le 10^9~, ~1 \le w_i \le 10^9~) cho biết hướng và chi phí lắp ráp động cơ ở vị trí thứ ~i~.

Output

• Ghi ra một số nguyên duy nhất là tổng chi phí nhỏ nhất để lắp ráp động cơ sao cho tàu có thể đi đến mọi điểm. Trong trường hợp không tồn tại các lắp ráp động cơ thỏa yêu cầu đề bài, hãy ghi ra ~-1~.

Sample Input 1

7
0 3 2
0 3 3
1 -1 3
-2 4 2
-4 0 1
2 1 2
0 0 1

Sample Output 1

6

Sample Input 2

2
1 0 10
0 1 10

Sample Output 2

-1