#arc131d. [arc131_d]AtArcher
[arc131_d]AtArcher
Problem Statement
Ringo is participating in an archery contest AtArcher.
In AtArcher, a participant shoots arrows at a target on a number line to compete for the total score. The center of the target is at coordinate . Based on where the arrow hits, the score of the shot is defined as follows.
- For , if the arrow hits a point whose distance from the center of the target is between and , the score is . If the distance is greater than , the score is . If the arrow hits the boundary, the higher score is applied.
- The closer to the center, the higher the score is. In other words, the following is satisfied.
- $0 = r_0 \\lt r_1 \\lt \\cdots \\lt r_{M-1} \\lt r_M$
For example, the figure below shows the score for a shot when .
Additionally, AtArcher has one special rule: the distance between any two arrows must always be at least . Violating this rule disqualifies the participant, making the total score .
What is the maximum total score that Ringo can get from all the shots?
Constraints
- $0 = r_0 \\lt r_1 \\lt \\cdots \\lt r_{M-1} \\lt r_M \\leq 10^{11}$
- $10^{11} \\geq s_0 \\gt s_1 \\gt \\cdots \\gt s_{M-1} \\gt 0$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the answer.
Sample Input 1
3 3 3
0 2 7 9
100 70 30
Sample Output 1
270
This sample input corresponds to the case in the Problem Statement, with .
For example, if the arrows hit the coordinates , they score , respectively, for a total score of , which is the maximum achievable.
Note that you cannot hit the -point area with all the arrows to score , because the distance between any two arrows must be at least , or you will be disqualified and score .
Sample Input 2
3 3 8
0 2 7 9
100 70 30
Sample Output 2
200
This sample input corresponds to the case in the Problem Statement, with .
For example, if the arrows hit the coordinates , they score , respectively, for a total score of , which is the maximum achievable.
Sample Input 3
7 5 47
0 10 40 100 160 220
50 25 9 6 3
Sample Output 3
111
For example, if you shoot the arrows as shown in the following figure, you will score in total, which is the maximum.
Sample Input 4
100 1 5
0 7
100000000000
Sample Output 4
300000000000
You can shoot arrows, but in order to avoid disqualification, at most arrows can hit the area with a positive score.
Sample Input 5
15 10 85
0 122 244 366 488 610 732 854 976 1098 1220
10 9 8 7 6 5 4 3 2 1
Sample Output 5
119