Bài tập

Cho \(n\) đoạn trên trục số, mỗi đoạn được biểu thị bởi cặp số nguyên dương \([l, r]\) trong đó \(l \le r\). Các đoạn này đôi một không có điểm chung hoặc chỉ có điểm chung ở đầu mút. Bạn được cho \(q\) truy vấn, mỗi truy vấn gồm hai số nguyên \((x, y)\) trong đó \(1 \le x \le y \le n\). Với mỗi truy vấn, bạn phải tìm số nguyên không âm \(k\) nhỏ nhất sao cho tồn tại cách nới rộng mỗi đoạn từ đoạn thứ \(x\) đến đoạn thứ \(y\) ra không quá \(k\) đơn vị để với mọi \(x \le i < y\) đoạn thứ \(i\) có giao điểm với đoạn thứ \(i+1\). Lưu ý với mỗi đoạn bạn chỉ được nới rộng sang trái và sang phải một số nguyên đơn vị mà thôi.

Ví dụ, khi \(n = 3\) và có 3 đoạn là \((1, 2), (4, 7), (12, 17)\):

• Nếu truy vấn \(x = 1\) và \(y = 2\) thì \(k\) nhỏ nhất bằng 1, khi đó ta có thể nới đoạn \((1,2)\) sang phải 1 đơn vị để được đoạn \((1,3)\) và nới đoạn \((4,7)\) sang trái 1 đơn vị để được đoạn \((3,7)\), lúc ấy hai đoạn \((1,3)\) và \((3,7)\) giao nhau.

• Nếu truy vấn \(x = 2\) và \(y = 3\) thì \(k\) nhỏ nhất bằng 3, khi đó ta có thể nới đoạn \((4,7)\) sang phải 3 đơn vị để được đoạn \((4,10)\) và nới đoạn \((12,17)\) sang trái 2 đơn vị để được đoạn \((10,17)\), lúc ấy hai đoạn \((4,10)\) và \((10,17)\) giao nhau.

• Nếu truy vấn \(x = 1\) và \(y = 3\) thì \(k\) nhỏ nhất bằng 3, khi đó ta có thể nới đoạn \((1,2)\) sang phải 1 đơn vị để được đoạn \((1,3)\), nới đoạn \((4,7)\) sang trái 1 đơn vị và sang phải 2 đơn vị để được đoạn \((3,9)\), đồng thời nới đoạn \((12,17)\) sang trái 3 đơn vị để được đoạn \((9,17)\), lúc ấy ba đoạn \((1,3)\), \((3,9)\), \((9,17)\) lần lượt giao nhau.

Input

• Dòng đầu là hai số nguyên \(n\) và \(q\) \((1 \le n \le 5000, 1 \le q \le 10^6)\).
• Dòng thứ \(i\) trong số \(n\) dòng tiếp theo mô tả đoạn thứ \(i\) gồm hai đầu mút \(l_i, r_i\) \((1 \le l_i < r_i \le 10^9)\). Lưu ý \(r_i \le l_{i+1}\) với mọi \(1 \le i < n\).
• Mỗi dòng trong số \(q\) dòng tiếp theo mô tả một truy vấn gồm hai số nguyên \(x, y\) \((1 \le x \le y \le n)\).

Output

• In ra \(q\) dòng, mỗi dòng gồm một số nguyên là số \(k\) nhỏ nhất tìm được cho truy vấn tương ứng.

Example

10 7
4 5
17 18
21 23
25 26
29 31
45 51
61 65
76 77
79 81
85 88
3 6
3 5
6 9
1 1
1 10
7 8
1 3

7
2
7
0
9
6
6

Scoring

\begintabular|c|c|l|
\hline
Subtask & Số điểm & Ràng buộc

\hline
1 & 15 & \(1 \le n, q \le 2000\), \(l_{i+1} \le r_i + 20\) với mọi \(i\)

\hline
2 & 25 & \(1 \le n, q \le 2000\)

\hline
3 & 60 & Không có ràng buộc gì thêm

\hline
\endtabular

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\)