Cho một cây gồm \(n\) đỉnh, đánh số từ \(1\) đến \(n\). Mỗi đỉnh \(i\) có trọng số không âm \(a_i\). Mỗi cạnh có trọng số không âm \(w_e\).

Bạn cần chọn đúng \(k\) đỉnh. Giá trị nhận được bằng tổng trọng số của các đỉnh được chọn, trừ đi tổng trọng số nhỏ nhất của các cạnh cần dùng để nối tất cả các đỉnh được chọn thành một cây con liên thông.

Nói cách khác, với tập \(S\) gồm đúng \(k\) đỉnh được chọn, gọi \(E(S)\) là tập cạnh của cây con nhỏ nhất chứa tất cả các đỉnh trong \(S\). Cần tối đa hóa:

Input

• Dòng đầu chứa hai số nguyên \(n, k\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\).
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\), mô tả một cạnh của cây.

Output

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

Constraints

• \(1 \le k \le n \le 5000\)
• \(0 \le a_i \le 10^9\)
• \(0 \le w_e \le 10^9\)

Example

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

10

8 4
26 6 46 39 34 44 42 32
1 2 20
1 3 6
2 4 24
2 5 26
3 6 29
3 7 27
4 8 24

96

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(10\%\) số điểm): \(w_e = 0\) với mọi cạnh.
• Subtask \(3\) (\(10\%\) số điểm): \(k \le 2\).
• Subtask \(4\) (\(15\%\) số điểm): Cây là một đường thẳng.
• Subtask \(5\) (\(15\%\) số điểm): Tồn tại số nguyên \(W\) sao cho mọi cạnh đều có trọng số \(W\) và \(W > a_1 + a_2 + \dots + a_n\).
• Subtask \(6\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(7\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.