Hôm nay bạn sẽ dẫn đầu một nhóm cung thủ yêu tinh để bảo vệ lâu đài bị tấn công bởi một đội quân Orc giận dữ. Ba mặt của lâu đài được bảo vệ bởi những ngọn núi không thể vượt qua và mặt còn lại được bao phủ bởi một bức tường dài được chia thành \(n\) phần. Tại thời điểm này, có chính xác \(a_i\) cung thủ đứng ở phần thứ \(i\) của bức tường này. Bạn biết rằng cung thủ đứng ở phần i có thể bắn những con Orc tấn công phần nằm ở khoảng cách không quá \(r\) , đó là tất cả những phần \(j\) sao cho \(|i-j| \le r\). Đặc biệt, \(r = 0\) có nghĩa là cung thủ chỉ có thể bắn vào lũ Orc tấn công phần \(i\).

Biểu thị của <u>cấp độ phòng thủ</u> của phần \(i\) là tổng số cung thủ có thể bắn vào lũ Orc tấn công phần này. <u>Độ tin cậy</u> của kế hoạch phòng thủ là giá trị tối thiểu của mức độ phòng thủ của phần tường riêng lẻ.

Chỉ còn một ít thời gian nữa là đến cuộc tấn công nên bạn không thể phân bổ lại các cung thủ đã ở trên tường. Tuy nhiên, có một lượng dự trữ \(k\) cung thủ mà bạn có thể phân phối giữa các phần tường theo cách tùy ý, tuy nhiên với phần thứ \(i\) có sức chứa tối đa là \(b_i\) cung thủ. Bạn muốn đạt được độ tin cậy tối đa có thể của kế hoạch phòng thủ.

Input

• Dòng đầu tiên của đầu vào chứa ba số nguyên \(n, r\) và \(k\) \((1 \le n \le 500 000, 0 \le r \le n, 0 \le k \le 10^{18})\) - số phần của bức tường, khoảng cách tối đa đến phần khác cung thủ vẫn có thể bắn và số lượng cung thủ chưa được phân bố dọc theo bức tường.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n ( 0 \le a_i \le 10^9)\) - số lượng cung thủ hiện tại ở mỗi phần.
• Dòng thứ ba chứa \(n\) số nguyên \(b_1, b_2, \dots, b_n ( a_i \le b_i \le 2 \times 10^{18})\) - sức chữa tối đa ở mỗi phần.

Output

• In một số nguyên - giá trị tối đa có thể có của độ tin cậy của kế hoạch phòng thủ, tức là giá trị lớn nhất có thể có của cấp phòng thủ tối thiểu nếu chúng ta phân phối tối ưu \(k\) cung thủ bổ sung

Scoring

• Subtask \(1\) (\(32\%\) số điểm) \(n \le 5000\)
• Subtask \(2\) (\(28\%\) số điểm) \(b[i] = 2 \times 10^{18}\)
• Subtask \(3\) (\(40\%\) số điểm) \(n \le 500000\)

Example

8 2 100
0 1 0 1 2 0 0 3
10 13 15 21 17 26 42 31        

38