Cho dãy số nguyên dương ~a[1], a[2], …, a[N]~. Xét cách chia dãy số ~a~ thành ~K~ nhóm sao cho mỗi nhóm chứa một đoạn liên tiếp các phần tử của ~a~. Gọi trọng số của một cách chia là tổng các phần tử lớn nhất của mỗi nhóm

Yêu cầu: Tìm cách chia dãy số ~a~ thành ~K~ nhóm sao cho trọng số của cách chia là nhỏ nhất

Dữ liệu

• Dòng 1: 2 số nguyên dương ~N~ và ~K~ (~K \le N~)
• Dòng 2: Gồm ~N~ số nguyên dương ~a[1], a[2], …, a[N]~

Kết quả:

• Ghi ra 1 số nguyên duy nhất là trọng số tìm được

Input 1

5 1
1 2 3 4 5   

Output 1

5

Input 2

5 2
1 2 3 4 5   

Output 2

6

Giới hạn:

• 14% số điểm: ~1\le N\le100, K\le min(N, 5)~
• 18% số điểm: ~1\le N\le20~
• 21% số điểm: ~1\le N\le100~
• 47% số điểm: ~1\le N\le100000, K\le min(N, 100).~

Thuật toán sắp xếp nổi bọt để sắp xếp không giảm một dãy số nguyên ~b~ độ dài ~m~, có thể được mô tả như sau:

• Bước 1: nếu dãy ~b~ là một dãy không giảm thì kết thúc thuật toán

• Bước 2: Chọn một vị trí ~i~ (~1 \le i < m~) nhỏ nhất mà ~b_i > b_{i + 1}~, tráo đổi giá trị của hai phần tử ~b_i~ và ~b_{i + 1}~. Tiếp tục quay lại Bước 1.

Cho một dãy số nguyên ~a~ độ dài ~n~, số thứ ~i~ là ~a_i~ (~|a_i| \le 10^9~). Đếm số cách chia dãy ~a~ thành các dãy đẹp liên tiếp, chia dư cho (~10^9 + 7~).

Một dãy liên tiếp được gọi là dãy đẹp nếu số bước để sắp xếp không giảm dãy đó bằng thuật toán sắp xếp nổi bọt nêu trên, sử dụng không qua ~k~ (~k \le n^3~) lần tráo đổi giá trị ở Bước 2.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ (~n \le 2 \times 10^5~, ~k \le n^3~).

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~|a_i| \le 10^9~), các số cách nhau bởi ít nhất một dấu cách.

Output

• Gồm một số nguyên duy nhất là số cách chia dãy ~a~ thành các dãy đẹp liên tiếp thỏa mãn yêu cầu đề bài

Scoring

Sample

Một công ty có ~n~ văn phòng được đánh số từ ~1~ đến ~n~. Công ty này muốn lắp đặt một vài đường dây liên lạc hai chiều giữa các văn phòng, sao cho giữa mọi cặp văn phòng ~i, j~ (~i \neq j~) tồn tại ít nhất một đường liên lạc giữa chúng.

Có ~k~ nhà mạng cung cấp tổng cộng ~m~ đường dây liên lạc, trong đó đường dây thứ ~i~ kết nối văn phòng ~u_i~ và văn phòng ~v_i~, được vận hành bởi nhà mạng ~c_i~ và mất chi phí ~p_i~ đồng† để lắp đặt (lưu ý mỗi cặp văn phòng có thể có đường dây của nhiều nhà mạng).

Ngoài ra, để tăng tính cạnh tranh, cả ~k~ nhà mạng đều đang tổ chức chương trình tri ân khách hàng; cụ thể, nếu tổng chi phí lắp đặt mà công ty trả cho nhà mạng thứ ~j~ vượt quá ~s_j~ đồng, nhà mạng ~j~ sẽ giảm giá 50 % cho phần chi phí chênh lệch, nghĩa là công ty sẽ chỉ phải trả
~ x_j - \frac{\max(0,\,x_j - s_j)}{2} ~ đồng, với ~x_j~ là tổng chi phí trước khi áp dụng khuyến mãi.

Hãy tìm cách dựng mạng lưới liên lạc sao cho tổng chi phí là nhỏ nhất có thể. Vì ta có thể chứng minh là tổng chi phí nhỏ nhất nhân 2 là một số nguyên, bạn cần in ra tổng chi phí nhỏ nhất nhân 2.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n, m, k~ (~2 \le n \le 1000~, ~n - 1 \le m \le 5\cdot 10^5~, ~1 \le k \le 10~) — số lượng văn phòng của công ty, số lượng đường dây có thể lắp đặt, và số lượng nhà mạng.
• Tiếp theo là ~m~ dòng, mỗi dòng gồm bốn số nguyên dương ~u_i, v_i, c_i, p_i~ (~1 \le u_i, v_i \le n~, ~u_i \neq v_i~, ~1 \le c_i \le k~, ~1 \le p_i \le 10^9~), mô tả đường dây thứ ~i~.
• Dòng cuối cùng gồm ~k~ số nguyên dương ~s_1, s_2, \dots, s_k~ (~1 \le s_j \le 10^9~), mô tả chi tiết chương trình tri ân khách hàng của ~k~ nhà mạng.

Đảm bảo tồn tại ít nhất một cách dựng mạng lưới liên lạc kết nối tất cả ~n~ văn phòng.

Output

In ra một số nguyên là tổng chi phí nhỏ nhất để dựng mạng lưới liên lạc nhân 2.

Sample Input 1

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

Sample Output 1

13

Sample Input 2

5 7 3
1 5 3 100
1 2 1 5
4 5 1 5
1 3 2 7
2 3 3 10
1 2 2 4
4 5 2 4
5 20 100

Sample Output 2

225

Đối với mỗi số tự nhiên ~x~, ta định nghĩa hàm trọng số của ~x~ là ~f(x)~ có công thức như sau:

• ~f(x) = ~ tổng của các số sinh ra từ các đoạn con liên tiếp của ~x~ dưới dạng cơ số ~10~.
• Ví dụ: ~f(1004) = 1 + 10 + 100 + 1004 + 0 + 00 + 004 + 0 + 04 + 4 = 1136~.

Bạn được nhận hai số nguyên dương ~n~ và ~k~. Xét tập ~S~ là tập các số nguyên dương gồm ~n~ chữ số, tất cả các chữ số đều bé hơn hoặc bằng ~7~ và chúng không có số ~0~ đứng đầu, hãy đếm số bộ ~(x,y,z) \in S~ thỏa mãn ~x < y < z~ và tổng ~(f(x) + f(y) + f(z))~ chia hết cho ~k~.

Input

• Gồm hai số nguyên dương ~n, k~

Output

• Ghi một số nguyên duy nhất là số bộ ba tìm được, chỉ cần in ra kết quả sau khi chia lấy dư cho ~10^9+7.~.

Subtask

• Có ~8\%~ test với ~n≤6;k≤10~
• Có ~20\%~ test với ~n≤9;k≤100~
• Có ~28\%~ test với ~n≤100;k≤100~
• Có ~44\%~ test với ~n≤1000;k≤1000~

Example

Sample input

1 7

Sample output

5

Sample input

3 30

Sample output

494146

Cho lưới ô vuông kích thước ~n~ x ~n~, các hàng đánh số ~1…n~ từ trên xuống dưới, các cột đánh số ~1…n~ từ trái sang phải. Mỗi ô trong lưới chứa một kí tự chữ cái latin in hoa. Xét các đường đi từ ô ~(1;1)~ đến ô ~(n;n)~ chỉ đi từ một ô sang ô kề cạnh bên phải hoặc bên dưới. Mỗi đường đi được đại diện bởi một xâu kí tự là dãy các kí tự trong các ô trên đường đi dọc theo hành trình. Đếm số đường đi có xâu đại diện là xâu đối xứng.

Input

• Dòng 1: số nguyên ~n~ ~(1 \leq n \leq 500)~.
• Dòng 2…~n+1~: dòng ~i+1~ chứa một xâu độ dài ~n~ mô tả hàng ~i~ của lưới.

Output

• Dòng 1: số nguyên là số lượng đường đi có xâu đại diện là xâu đối xứng, lấy phần dư khi chia cho ~(10^9+7)~.

Subtask

• Có ~30\%~ số test có ~n \le 100~
• ~70\%~ còn lại không giới hạn gì thêm

Sample Input 1

4
ABCD
BXZX
CDXB
WCBA

Sample Output 1

12

Explanation:

• Xâu ABCDCBA là đại diện của 1 đường
• Xâu ABCWCBA là đại diện của 1 đường
• Xâu ABXZXBA là đại diện của 6 đường
• Xâu ABXDXBA là đại diện của 4 đường

Cho một cây có trọng số gồm ~n~ đỉnh được đánh số từ ~1~ tới ~n~. Đỉnh ~u~ đang có ~p_u~ người. Cạnh nối giữa hai đỉnh ~u~ và ~v~ có trọng số là ~d(u,v)~.

Bạn có một phương tiện có thể di chuyển một lúc tối đa ~c~ người trong một chuyến. Đồng nghĩa với việc, để di chuyển ~x~ nhân viên từ hai đỉnh ~u~ và ~v~ kề với nhau thì sẽ tốn chi phí là ~\lceil \frac{x}{c} \rceil \times d(u,v)~.

Nhiệm vụ của bạn là tính ra tổng chi phí bé nhất để di chuyển mọi người sao cho số lượng người chênh lệch giữa các đỉnh trên cây là nhỏ nhất. Nói cách khác, gọi ~Max~ là số người nhiều nhất trên một đỉnh của cây sau khi di chuyển, tương tự ~Min~ là số người ít nhất, bạn cần tối ưu ~Max - Min~ bé nhất có thể.

Input

• Dòng đầu gồm hai số nguyên dương ~n~ và ~c~ ~(1 \le n \le 2000, 1 \le c \le 10^6)~
• Dòng thứ hai gồm ~n~ số nguyên không âm ~p_1, p_2, ..., p_n~ miêu tả số người trên mỗi đỉnh.
• ~n-1~ dòng cuối cùng, dòng thứ ~i~ gồm ba số nguyên ~u_i,v_i, d(u_i,v_i)~ miêu tả cạnh thứ ~i~ ~(1 \le u_i \le v_i \le n, 1 \le d(u_i,v_i) \le 10^6)~.

Output

• In ra tổng chi phí nhỏ nhất có thể để thỏa mãn yêu cầu đề bài.

Subtask

• Subtask ~1~: ~n = 3~ ~(20\%)~
• Subtask ~2~: ~n,c \le 100~ ~(30\%)~
• Subtask ~3~: Cây là đường thẳng ~(20\%)~
• Subtask ~4~: Không giới hạn gì thêm ~(30\%)~

Example

Sample Input 1

4 10
12 9 36 28
1 2 1
1 3 1
2 4 2

Sample Output 1

5