Alice has just earned her driving license and she can’t wait to go on a road trip!
Alice starts at city 1 and will visit cities 2,3,..., N in order. It takes T; time to drive from city i to
city i+1 (1
The most important thing for Alice to keep in mind of is her car’s fuel level — if the car runs out of
fuel in the middle of the road, Alice will be stranded! The car’s fuel tank capacity is C, and the fuel
level is initially full. Each unit of time of driving decreases fuel level by 1. Fortunately, at each city
there is a gas station. Adding one unit of fuel to the car at city ¢ takes R; time and costs D; dollars.
Alice can refuel as much as she wants, as long as the fuel level does not exceed C.
Alice is travelling on a budget and will
ing M dollars with her on the trip. Please determine the
minimum time needed to drive from city 1 to city N.
Input: The first line has three integers N, M, and C, respectively the number of cities, the budget,
and the fuel tank capacity. The second line has N — 1 integers 11,75, ...,Tn—_1, the time needed to
drive from city ¢ to city ¢ + 1. The third line has N integers Ry, Ra, ..., Rn, the unit time cost of fuel
in each city. The fourth line has N integers D1, Da, ..., Dy, the unit money cost of fuel in each city.
It is guaranteed that 2 < N < 20, 0 < M < 2000, and 1 < C < 500; 1
1 < D; < 2000. Furthermore, for test cases worth 90% of the points, it is guaranteed that 0 < M < 500
and 1 < C £100.
Output: If it is impossible to reach city N, output -1 on a single line. Otherwise, output two lines.
On the first line, output the minimum time needed to travel to city N. On the second line, output N
integers fi, fa,..., fn, where f; is the amount of fuel added to the car at city i.
If there are multiple refueling plans that minimize travel time, output any of them.
Sample Input 1:
XXXXXXXXXX
XXXXXXXXXX
11201
XXXXXXXXXX
Sample Output 1:
110
0500
Sample Input 2:
XXXXXXXXXX
XXXXXXXXXX
11201
XXXXXXXXXX
Sample Output 2:
205
0050
Sample Input 3:
XXXXXXXXXX
XXXXXXXXXX
11201
XXXXXXXXXX
Sample Output 3:
-1