Bài tập

Quân đang cần gấp \(M\) mét gỗ để đốt củi sưởi ấm mùa đông. May mắn là anh có một cái máy cưa có thể cắt mọi thứ, ở bất kì độ cao nào.

Máy cưa sẽ hoạt động như sau: Lúc đầu Quân sẽ chỉnh độ cao cắt của máy cưa, gọi độ cao đó là \(H\). Sau đó, máy cưa sẽ tự động bay lên, cắt một đường ngang, cây nào có độ cao lớn hơn \(H\) sẽ bị cắt trúng, và phần gỗ rơi xuống Quân sẽ lấy đi để đốt.

Ví dụ nếu các cây có độ cao lần lượt là \(20, 15, 15, 20, 25\), và \(H = 15\) thì cây thứ nhất và cây thứ tư mỗi cây bị cắt mất \(5\) m, cây thứ \(5\) bị cắt mất \(10\) m, tổng cộng là \(20\) m.

Yêu cầu: Hãy xác định độ cao \(H\) lớn nhất sao cho cắt ở độ cao \(H\) thì Quân sẽ thu được ít nhất \(M\) mét gỗ. Nếu cắt trụi \(N\) cây mà vẫn không đủ \(M\) mét gỗ, in ra \(-1\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) - số lượng cây.
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_{1}, a_{2}, ..., a_{N}\) - độ cao lần lượt của các cây.

Output

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

Example

4 7
20 15 10 17

15

5 20
4 42 40 26 46

36

Scoring

• \(50\%\) số test có \(N \leq 1000\), độ cao lớn nhất của các cây không vượt quá \(1000\) m.
• \(50\%\) số test còn lại có \(N \leq 10^6\), độ cao lớn nhất của các cây không vượt quá \(10^9\) m.

Đảm bảo trong tất cả các test, \(M \leq 10^9\).

Cho một cây có gốc gồm \(n\) nút. Các nút được đánh số từ \(1\) đến \(n\), và nút \(1\) là gốc của cây. Mỗi nút có một giá trị.

Bạn cần xử lý hai loại truy vấn sau:

• Cập nhật giá trị của một nút: Thay đổi giá trị của nút \(s\) thành \(x\).
• Tính tổng: Tính tổng giá trị của tất cả các nút trên đường đi từ gốc cây (nút \(1\)) đến nút \(s\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)), lần lượt là số lượng nút và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(v_1, v_2, \ldots, v_n\) (\(1 \le v_i \le 10^9\)), là giá trị ban đầu của các nút.
• \(n-1\) dòng tiếp theo mô tả các cạnh của cây. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) (\(1 \le a, b \le n\)), cho biết có một cạnh nối giữa hai nút \(a\) và \(b\).

• Cuối cùng là \(q\) dòng mô tả các truy vấn. Mỗi truy vấn có dạng:

• "1 s x": Thay đổi giá trị của nút \(s\) thành \(x\) (\(1 \le s \le n, 1 \le x \le 10^9\)).

• "2 s": Tính tổng giá trị trên đường đi từ gốc đến nút \(s\) (\(1 \le s \le n\)).

Output

• Với mỗi truy vấn loại 2, in ra tổng giá trị tính được trên một dòng.

Example

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

9
9

Scoring

• Subtask 1 (30 điểm): \(n, q \le 1000\).
• Subtask 2 (70 điểm): Không có ràng buộc gì thêm.

Lục địa QT có tổng cộng \(N\) đất nước (được đánh số từ \(1\) đến \(N\)) và có \(M\) con đường hai chiều nối giữa các đất nước với nhau. Đất nước RoNE có chỉ số là \(1\), và đất nước NhaNTH có chỉ số là \(N\). Quân đội của đất nước RoNE có \(X\) quân lính và đang muốn xuất quân đi đánh chiếm đất nước thực dân NhaNTH.

Ở mỗi đất nước trên lục địa QT đều có quân thực dân của đất nước NhaNTH chiếm đóng (kể cả đất nước của RoNE), đất nước thứ \(i\) có \(A_i\) quân thực dân. Khi đội quân của RoNE đi qua một đất nước, sẽ có một trận chiến xảy ra. Nếu số lượng quân của RoNE nhiều hơn số lượng quân thực dân tại đất nước đó, quân đội RoNE sẽ toàn thắng, chiếm được đất nước đó và không có thiệt hại nào. Ngược lại, đội quân RoNE vẫn sẽ chiến thắng và chiếm được đất nước đó nhưng số lượng quân sống sót chỉ còn một nửa (nếu số lượng quân lính của RoNE là \(x\) thì sẽ chỉ còn lại \(\lfloor \frac{x}{2}\rfloor\)). Đội quân RoNE cần phải bắt đầu từ đất nước của mình đến đất nước NhaNTH và tiêu diệt tất cả quân thực dân trên đường đi.

Nếu bạn là quân sư của đất nước RoNE, hãy tìm một đường hành quân tốt nhất sao cho có thể bảo toàn được nhiều quân lính nhất có thể sau khi chiếm được đất nước NhaNTH.

Input

• Dòng đầu tiên gồm \(2\) số \(N,M\) là số lượng đất nước và số lượng đường đi giữa các đất nước.
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) mô tả một con đường nối giữa hai đất nước \(u\) và \(v\).
• Dòng tiếp theo chứa số nguyên \(X\ (1\le X\le10^9)\) là số lượng quân lính của đất nước RoNE.
• Dòng tiếp theo chứa \(N\) số nguyên dương mô tả dãy \(A\ (1\le A_i\le10^9)\) là số lượng quân thực dân tại mỗi đất nước.

Output

• Ghi ra số lượng quân lính tối đa có thể sống sót sau khi chiếm được đất nước NhaNTH. Nếu không thể chiếm đánh thành công, ghi ra \(0\).

Example

4 4
1 2
1 3
2 4
3 4
7
10 2 3 1

3

4 4
1 2
1 3
2 4
3 4
7
10 3 3 1

0

Scoring

• Subtask \(1\) (\(20\%\) số điểm) \(1 \le N,M \le 1000\).
• Subtask \(2\) (\(30\%\) số điểm) \(1 \le N,M \le 100000\).
• Subtask \(3\) (\(50\%\) số điểm) \(1 \le N, M \le 500000\).

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