The organizers of the IDDA Cup are arranging T-shirts for the final round, with n gift- presenters and n boxes at their disposal. Each gift-presenter is currently holding a specific number of T-shirts in their hands, and each box has a predetermined capacity for holding T-shirts. The number of T-shirts in the i-th gift-presenter’s hands is ai and the capacity of the i-th box is bi. Currently the boxes are empty and organizers want to distribute the T-shirts that the gift-presenters hold to the boxes so that they can rest a bit. However, they cannot exceed the capacity of any box.
For each gift-presenter numbered from 1 to n, the T-shirts that the i-th of them holds can be placed in the i-th and (i mod n+1)-th box.
Find the maximum number of T-shirts that can be distributed into boxes, if organizers make the optimal distribution.
Contains zero or more test cases, and is terminated by end-of-file. For each test case:
The first line contains an integer n (3≤n≤106).
The second line contains n integers a1,a2,...,an (0≤ai≤109).
The third line contains n integers b1,b2,...,bn (0≤bi≤109).
It is guaranteed that the sum of all n does not exceed 106.
For each test case, print in a new line the maximum number of T-Shirts that can be distributed into boxes.
This task consists of the following subtasks. If all tests of a subtask are passed, you will earn points for that subtask.
(15 points): n≤10, ai,bi≤10;
(25 points): n≤10, ai,bi≤100;
(60 points): no additional constrains;