Bài tập

Đất nước "vui vẻ" có \(n\) thành phố được đánh số từ \(1\) đến \(n\), và \(n − 1\) con đường hai chiều nối một số cắp thành phố. Giữa hai thành phố bất kỳ luôn có đường đi trực tiếp hoặc đường đi gián tiếp qua một số thành phố trung gian.

Có \(k\) thành phố nổi tiếng mà khách du lịch luôn muốn đến thăm. Khách du lịch sẽ bắt đầu từ một thành phố nào đó trong \(n\) thành phố, đi theo các con đường nối giữa các thành phố để thăm đủ k thành phố nổi tiếng (mỗi con đường/thành phố có thể đi qua nhiều lần). Đất nước khá là vui vẻ trừ giá taxi ở đây, nên khách du lịch muốn chọn
lộ trình có tổng độ dài phải đi là nhỏ nhất. Nhưng bạn biết đấy, sẽ thật phiền phức khi vừa đi du lịch vừa phải code, họ sẽ rất vui vẻ nếu nhận được sự giúp đỡ của bạn

Input

• Dòng đầu chứa hai số nguyên dương \(n\), \(k\)

• \(n − 1\) dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên dương \(u, v, L\); cho biết có một con đường độ dài \(L\) nối giữa hai thành phố \(u, v\)

• Dòng tiếp theo chứa \(k\) số nguyên dương là số hiệu của \(k\) thành phố nổi tiếng

Output

Gồm n dòng, dòng thứ \(i\) là tổng độ dài phải đi của lộ trình tốt nhất nếu khách du lịch bắt đầu từ thành phố \(i\)

Example

13 5
1 2 1
2 3 1
3 4 1
2 5 1
1 7 1
6 7 1
7 10 1
1 8 1
8 9 1
8 11 1
8 12 1
12 13 1
2 4 7 9 13

13
12
11
10
13
13
12
12
11
13
13
11
10

Scoring

• \(1 ≤ k ≤ n ≤ 10^5\)

• \(1 ≤ L ≤ 10^9\)

• Có \(50\%\) số test với \(n ≤ 1000\).

Quân có một dãy số nguyên \(a_{1}, a_{2}, ..., a_{n}\). Dãy có thể có số âm hoặc số dương, nhưng Quân không thích số \(0\).

Quân cực kì ghét những dãy con liên tiếp có tổng bằng \(0\). Bạn cần giúp Quân chèn thêm vài số vào trong dãy, sao cho sau khi chèn, không tồn tại dãy con liên tiếp có tổng bằng \(0\). Bạn chỉ có thể chèn số vào giữa hai phần tử kề nhau trong dãy số. Và trong những cách chèn số, chọn ra cách có số lượng số chèn vào là ít nhất.

Input

Dòng đầu tiên gồm một số nguyên dương \(n\) - số lượng phần tử của dãy.

Dòng thứ hai gồm \(n\) số nguyên \(a_{1}, a_{2}, ..., a_{n}\) \((-10^9 <= a_{i} <= 10^9, a_{i} \neq 0)\).

Output

Một số nguyên không âm duy nhất là kết quả bài toán

Example

4
1 -5 3 2

1

5
4 -2 3 -9 2

0

9
-1 1 -1 1 -1 1 1 -1 -1

6

Scoring

Có \(40\%\) \(n <= 20\).

\(60\%\) còn lại \(n <= 200000\).

Thành oai hùng ngày nào nay đã trở thành bảo vệ của rừng BaNgocLand(có dạng hình chữ nhật kích thước \(m \times n\)). Để đền đáp công lao to lớn của Thành, Chúa đất cho phép anh chọn một vùng đất hình chữ nhật có kích thước \(k \times k\), có các cạnh song song với các bìa rừng, khai thác tài nguyên tại vùng đất này để lây kinh phí dựng nhà, lấy vợ.

Chúa đất chỉ cho phép anh khai thác cây trong đúng vùng đất mà anh ấy chọn. Biết giá trị của mỗi cây trong khu rừng AnLuuLand tại vị trí dòng \(i\) cột \(j\) là \(a_{i, j}\) nguyên. Bạn hãy giúp Thành chọn một vùng đất có giá trị cao nhất mà vẫn thỏa mãn yêu cầu của Chúa đất. Thành có thể không chọn nếu muốn.

Input

Dòng 1: Gồm \(3\) số nguyên dương \(m, n, k\) \((m, n, k \leq 700)\).

\(m\) dòng sau, mỗi dòng gồm \(n\) số nguyên là giá trị của mỗi cây trong khu rừng. Giá trị của mỗi cây là một số nguyên có trị tuyệt đối không quá \(10^9\).

Output

Một số duy nhất là giá trị cao nhất mà Thành có thể nhận được.

Example

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

18