2025.05.16

Bạn đang chơi Minecraft, công việc của bạn là phải xây dựng một bức tường có độ cao lớn nhất có thể. Hiện tại, bạn đang có sẵn một bức tường có \(n\) cột, cột thứ \(i\) có chiều cao là \(a_{i}\). Hiện tại bạn có \(w\) khối, với mỗi khối bạn có thể nâng độ cao một cột bất kì thêm một đơn vị. Bạn muốn xây bức tường sao cho độ cao của cột có độ cao nhỏ nhất là lớn nhất có thể. Hỏi độ cao đó có thể bằng bao nhiêu?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(w\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq w \leq 10^{9})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \le 10^{9})\).

Output

• Một dòng chứa một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 100, w \leq 10^{5}\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^{3}, w \leq 10^{6}\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3 9 
1 1 1

4

Có \(n\) học sinh đang xếp hàng từ trái sang phải. Mỗi học sinh được nhận diện bằng mã số sinh viên là \(ID\). Để thách đố học sinh của mình, thầy chủ nhiệm đã phát cho mỗi em học sinh một mảnh giấy để ghi lại mã số sinh viên lần lượt của bạn đứng trước (xếp bên trái) và sau đó là bạn đứng sau mình (xếp bên phải). Trong trường hợp không có bạn nào ở trước hoặc ở sau thì học sinh sẽ điền giá trị 0.

Sau khi đã viết lên giấy xong, thầy bắt đầu thu hồi lại các mảnh giấy và sắp xếp lại các mảnh giấy theo một trình tự ngẫu nhiên. Sau đó thầy hỏi các bạn về thứ tự xếp hàng ban đầu.

Cho dữ liệu về số học sinh \(n\) và nội dung theo đúng trình tự của các mảnh giấy. Hãy cho biết ban đầu, các học sinh đã xếp hàng như thế nào?

Input

• Dòng đầu tiên là số nguyên dương \(n\) (\(n \leq 2 \times 10^5\)) là số học sinh đã tham gia xếp hàng.
• \(n\) dòng tiếp theo: mỗi dòng là hai số nguyên dương \(a_{i}\) và \(b_{i}\) \((a_{i}, b_{i} \leq 10^6)\) lần lượt là \(ID\) của bạn đứng trước và \(ID\) của bạn đứng sau. Nếu \(a_{i} = 0\) thì không có bạn nào đứng trước và nếu \(b_{i} = 0\) thì không có bạn nào đứng sau.

Output

• Gồm \(n\) số nguyên dương là \(ID\) của các bạn theo trình tự xếp hàng ban đầu từ trái sang phải của các bạn học sinh.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(80\%\) số điểm): Không ràng buộc gì thêm.

Example

5
1 3
0 5
5 2
3 4
2 0

1 5 3 2 4