Pak Chanek observes that the carriages of a train is always full on morning departure hours and afternoon departure hours. Therefore, the balance between carriages is needed so that it is not too crowded in only a few carriages.
A train contains \(N\) carriages that are numbered from \(1\) to \(N\) from left to right. Carriage \(i\) initially contains \(A_i\) passengers. All carriages are connected by carriage doors, namely for each \(i\) (\(1\leq i\leq N-1\)), carriage \(i\) and carriage \(i+1\) are connected by a two-way door.
Each passenger can move between carriages, but train regulation regulates that for each \(i\), a passenger that starts from carriage \(i\) cannot go through more than \(D_i\) doors.
Define \(Z\) as the most number of passengers in one same carriage after moving. Pak Chanek asks, what is the minimum possible value of \(Z\)?
Output
An integer representing the minimum possible value of \(Z\).
Note
One strategy that is optimal is as follows:
- \(5\) people in carriage \(1\) move to carriage \(4\) (going through \(3\) doors).
- \(3\) people in carriage \(5\) move to carriage \(3\) (going through \(2\) doors).
- \(2\) people in carriage \(6\) move to carriage \(5\) (going through \(1\) door).
- \(1\) person in carriage \(6\) moves to carriage \(7\) (going through \(1\) door).
The number of passengers in each carriage becomes \([2,4,5,5,4,5,4]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
7 4 2 0 5 8 3
4 0 0 1 3 1 3
|
5
|