There are N students living in the dormitory of Berland State University. Each of them sometimes wants to use the kitchen, so the head of the dormitory came up with a timetable for kitchen's usage in order to avoid the conflicts:
- The first student starts to use the kitchen at the time 0 and should finish the cooking not later than at the time A1.
- The second student starts to use the kitchen at the time A1 and should finish the cooking not later than at the time A2.
- And so on.
- The N-th student starts to use the kitchen at the time AN-1 and should finish the cooking not later than at the time AN
The holidays in Berland are approaching, so today each of these N students wants to cook some pancakes. The i-th student needs Bi units of time to cook.