Minimize Fuel Cost for Sunrise Journey

Little R is determined to watch the sunrise and has traveled to the eastern coast of country C. The coastline has n cities numbered from 1 to n going from north to south. City with a smaller number lies to the north of one with a larger number. Adjacent cities (i and i+1) are connected by a coastal highway with a length of \(l_i\) kilometers.

Little R has a car that uses one unit of gasoline per kilometer. However, there are no gas stations along the roads – he can only refuel in the cities. City \(i\) sells gasoline at a price of \(p_i\) per unit. The car’s fuel tank has a capacity of \(V\) units; if the fuel runs out, the car stops immediately and cannot move further.

Little R has planned m trips to watch the sunrise. In the \(i\)th trip, he starts at city \(s_i\) (where he parked his car the previous night) and must drive to city \(t_i\) (with \(s_i < t_i\)) early in the morning. Since he always takes the shortest route, he will travel through cities \(s_i, s_i+1, \ldots, t_i\) consecutively. At the beginning of the \(i\)th trip, the car has \(v_i\) units of fuel (where \(0 \le v_i \le V\)).

Little R wants to plan his refueling stops optimally so that the total refueling cost is minimized for each trip. If it is impossible to complete a trip, output –1.

Note: Each trip is independent — the fuel remaining at the end of one trip does not affect the next.

Input/Output Format are described below.

inputFormat

The input begins with a line containing three integers: \(n\), \(m\), and \(V\) representing the number of cities, the number of trips, and the fuel tank capacity, respectively.

The next line contains \(n-1\) integers: \(l_1, l_2, \ldots, l_{n-1}\) where \(l_i\) is the distance (in kilometers) between city \(i\) and city \(i+1\).

The following line contains \(n\) integers: \(p_1, p_2, \ldots, p_n\) where \(p_i\) is the cost per unit of fuel in city \(i\).

Then, there are \(m\) lines, each containing three integers: \(s_i\), \(t_i\), and \(v_i\) representing the starting city, destination city, and the initial amount of fuel in the car for the \(i\)th trip. It is guaranteed that \(s_i < t_i\).

outputFormat

For each trip, output a single line with the minimum total refueling cost to reach the destination. If the trip is impossible, output -1 instead.

sample

5 3 10
5 5 5 5
5 2 4 1 3
1 5 5
2 4 5
4 5 10

25
10
0