Bài tập

Khu Trang ở có \(N\) ngôi nhà đánh số từ \(1\) đến \(N\), các ngôi nhà được nối với nhau bởi các con đường. Từ một ngôi nhà bất kỳ sang một ngôi nhà khác luôn có một và chỉ một con đường một chiều, độ dài các con đường có thể không giống nhau. Nhà Trang là ngôi nhà số \(1\). Một ngày nọ, Trang nhận được đơn đặt hàng của \(K\) ngôi nhà khác, Trang cần tìm ra lộ trình, xuất phát từ nhà, đi tới các ngôi nhà để giao hàng, và quay trở về nhà; sao cho tổng độ dài đường đi là nhỏ nhất.

Do điều kiện khó khăn, Trang chỉ mua được Ipod, Itouch, Iphone, Ipad, Iwatch mà chưa đủ tiền mua MacBook. Vì vậy, Trang cần sự giúp đỡ của các bạn để tìm ra độ dài đường đi ngắn nhất. Các bạn hãy giúp Trang nhé!

Input

Dòng đầu tiên chứa số nguyên \(N\) là số ngôi nhà, và số nguyên \(K\) là số ngôi nhà có đơn đặt hàng. \((2 ≤ N ≤500,1 ≤ K < N)\)

\(N\) dòng tiếp theo, mỗi dòng gồm \(N\) số nguyên. Số thứ \(j\) trong dòng thứ \(i\) (ký hiệu \(c_{i, j}\)) là độ dài đường đi từ ngôi nhà \(i\) tới ngôi nhà \(j\). \((0 ≤ c_{i,j} ≤ 10^8\), \(c_{i,i} = 0\)).

Dòng cuối cùng chứa \(K\) số nguyên phân biệt là \(K\) ngôi nhà có đơn đặt hàng. Ngôi nhà số \(1\)
không có đơn đặt hàng.

Output

In ra một số nguyên duy nhất là độ dài lộ trình nhỏ nhất tìm được.

Example

5 3
0 6 10 8 7
10 0 9 7 9
9 9 0 10 7
8 10 9 0 8
7 9 9 7 0
4 5 2

28

Có thể nhận thấy ở thời điểm hiện tại, ngành công nghiệp game Esport ngày càng phát triển. Khi nói đến tựa game Esport nổi tiếng và hấp dẫn nhất, không thể thiếu Liên Minh Huyền Thoại (League of Legends). Với mức độ phủ sóng khủng khiếp trên toàn cầu nên các giải đấu về trò chơi này luôn nhận được sự quan tâm của đông đảo người hâm mộ. Và giải đấu LCK cũng là một trong số đó.

LCK là viết tắt của League of Legends Champions Korea, trước đây được biết đến với tên Ongamenet LCK (OGN) và được tổ chức bởi 1Ongamenet, là đấu trường cao nhất của bộ môn thể thao điện tử Liên Minh Huyền Thoại tại Hàn Quốc". Hiện tại, LCK mùa hè \(2023\) đã chính thức khép lại với chiến thắng không thể bàn cãi của GenG.

Fekar - một trong những tuyển thủ huyền thoại của làng Liên Minh Huyền Thoại, sau một thời gian dài gắn bó đã giải nghệ. Fekar đã được đề cử lên làm trưởng ban tổ chức của giải đấu LCK. Vì một lí do nào đó, Fekar đã thay đổi cơ cấu của giải đấu này như sau:

Trước khi bắt đầu mùa giải, mỗi tuyển thủ đều sẽ có một huy hiệu hiển thị một số nguyên \(h_{i}\) - đại diện cho chỉ số kĩ năng của tuyển thủ đó (với \(i\) là số hiệu của tuyển thủ, có tất cả \(n\) tuyển thủ tham gia thi đấu). Thay vì thi đấu theo đội tuyển của mình với hình thức \(5\) vs \(5\), Fekar đã thay đổi luật, tất cả các tuyển thủ sẽ không theo một đội tuyển nào, xếp các tuyển thủ từ trái sang phải theo thứ tự từ \(1\) đến \(n\), sau đó sẽ chia lại các đội tuyển thi đấu (đồng nghĩa rằng bạn sẽ không biết đồng đội của bạn là ai). Fekar yêu cầu các tuyển thủ thuộc cùng một đội tuyển phải đứng sát nhau, một tuyển thủ phải thuộc chính xác một đội tuyển. Nói cách khác, một đội tuyển thi đấu sẽ là một đoạn con trên dãy các tuyển thủ. Quy định này sẽ không hạn chế người của một đội tuyển.

Fekar quy định sức mạnh của một đội tuyển là sự chênh lệnh giữa tuyển thủ có chỉ số kĩ năng cao nhất và tuyển thủ có chỉ số kĩ năng thấp nhất. Nói một cách "công thức" hơn,
nếu tuyển thủ đầu tiên của đội tuyển \(X\) có số thứ tự là \(i\), và tuyển thủ cuối cùng có số thứ tự là \(j\) \((1 \leq i \leq j \leq n)\), sức mạnh đội tuyển là giá trị \(max(h_{i}...h_{j}) - min(h_{i}...h_{j})\).

Gọi sức mạnh tổng thể của giải đấu là tổng sức mạnh của các đội tuyển, Fekar muốn giá trị này đạt càng lớn càng tốt, các bạn hãy giúp Fekar chia đội tuyển một cách hợp lí nhé!

Input

Dòng đầu tiên là số nguyên \(n\) - số tuyển thủ thi đấu \((2 \leq n \leq 10^6)\).

Dòng tiếp theo là \(n\) số nguyên \(h_{1}, h_{2}, h_{3}, ..., h_{n}\) \((-10^9 \leq h_{i} \leq 10^9)\).

Output

Kết quả bài toán.

Example

5
1 2 3 1 2

3

Scoring

\(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 20\).

\(20\%\) số test tương ứng với \(20\%\) số điểm, \(h_{i} <= h_{i + 1}\) \((1 \leq i < n)\).

\(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 5000\).

\(20\%\) số test tương ứng với \(20\%\) số test, \(h_{i} = a\) hoặc \(h_{i} = b\) với \(a, b\) là hằng số.

\(20\%\) số test còn lại không có ràng buộc gì thêm.

Trong buổi sinh hoạt đầu tiên của một câu lạc bộ, có \(n\) thành viên mới đứng thành một hàng ngang, được đánh số từ \(1\) đến \(n\). Thầy giáo chủ nhiệm muốn chia các bạn thành \(m\) nhóm để tiện cho việc sinh hoạt và làm quen. Mỗi nhóm phải bao gồm một dãy các học sinh đứng liên tiếp nhau trong hàng và mỗi nhóm phải có ít nhất một thành viên.

Tuy nhiên, thầy giáo hiểu rằng các bạn học sinh đến từ nhiều lớp khác nhau nên không phải ai cũng đã quen biết nhau. Thầy đã tiến hành một cuộc khảo sát để xác định "mức độ không quen biết" giữa từng cặp học sinh. Mức độ không quen biết giữa bạn thứ \(i\) và bạn thứ \(j\) được cho bởi một số nguyên \(a_{i,j}\).

Để các nhóm hoạt động hiệu quả, thầy giáo muốn sắp xếp các nhóm sao cho tổng mức độ không quen biết của tất cả các nhóm là nhỏ nhất. Mức độ không quen biết của một nhóm được định nghĩa là nửa tổng mức độ không quen biết của tất cả các cặp học sinh bất kỳ trong nhóm đó.

Với \(n\) học sinh đứng thành một hàng và \(m\) nhóm cần chia, cùng với ma trận mức độ không quen biết \(A = [a_{ij}]\), hãy tìm cách chia các học sinh thành \(m\) nhóm liên tiếp sao cho tổng mức độ không quen biết của tất cả các nhóm là nhỏ nhất.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\) (\(1 \le n \le 4000, 1 \le m \le \min(n, 800)\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(n\) số nguyên, số thứ \(j\) trên dòng thứ \(i\) là \(a_{ij}\) (\(0 \le a_{ij} \le 9, a_{ij} = a_{ji}, a_{ii} = 0\)).

Output

Một số nguyên duy nhất - tổng mức độ không quen biết nhỏ nhất của \(m\) nhóm

Example

3 2
0 2 0
2 0 3
0 3 0

2

Scoring

• Subtask \(1\) (\(30\%\) số điểm) : \(n \leq 20\).
• Subtask \(2\) (\(30\%\) số điểm) : \(n \leq 400\).
• Subtask \(3\) (\(40\%\) số điểm) : không có ràng buộc nào thêm.

Cho một cây có trọng số gồm \(n\) đỉnh. Cây là một đồ thị vô hướng liên thông không có chu trình.

Có \(m\) truy vấn, truy vấn thứ \(i\) là một số nguyên dương \(q_{i}\). Mỗi truy vấn bạn cần trả lời có bao nhiêu cặp \((u, v) (u < v)\) mà cạnh có trọng số lớn nhất trên đường đi từ đỉnh \(u\) đến đỉnh \(v\) có giá trị không vượt quá \(q_{i}\).

Input

Dòng đầu tiên gồm hai số nguyên dương \(n, m\) - số lượng đỉnh và số lượng truy vấn.

\(n - 1\) dòng tiếp theo, mỗi dòng gồm \(3\) số \(x, y, w\) - có cạnh nối đỉnh x và đỉnh y, cạnh đó có trọng số là \(w\). \((x, y <= n, w <= 10^9)\)

Dòng cuối cùng gồm \(m\) số nguyên dương \(q_{1}, q_{2}, ... , q_{m}\). \((q_{i} <= 10^9)\)

Output

Gồm \(m\) số, mỗi số cách nhau một dấu cách, là kết quả của các truy vấn.

Example

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

21 7 15 21 3 

1 2
1 2

0 0 

3 3
1 2 1
2 3 2
1 3 2

1 3 3 

Scoring

Có \(25\) phần trăm số test có \(n, m <= 20\)

Có \(25\) phần trăm số test có \(n, m <= 500\)

Có \(50\) phần trăm số test có \(n, m <= 2.10^5\)