Hôm nay Lộc muốn ăn socola nên đã đến cửa hàng để mua. Cửa hàng bán N loại socola khác nhau. Loại thứ i có ai viên socola có thể bán.
Lộc là thiếu gia tiền nhiều vô kể. Vì thế Lộc không bị giới hạn bởi bất kỳ giá tiền nào và muốn mua nhiều socola nhất có thể.
Tuy nhiên, nếu Lộc mua x_i socola loại i (0 \leq x_i \leq a_i) thì số lượng mua socola các loại j từ 1 đến i − 1 (1 \leq j \lt i) phải thỏa một trong hai điều kiện:
- x_j = 0. Lộc không mua socola loại j.
- $x_j < x_i$. Lộc mua được ít socola loại $j$ hơn loại $i$.
Ví dụ: Cửa hàng trưng bán số lượng socola các loại từ 1 đến N là: [6, 5, 4, 2, 5]. Mảng x = [0, 0, 1, 2, 5] là số lượng mua được socola các loại từ 1 đến N.
Bạn hãy tính số socola tối đa mà Lộc mua được ở cửa hàng
