Water Delivery

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

After skiing, ice skating, and other physical activities that the couple enjoyed on Valentine’s Day, it was time for the hot tub.

Unfortunately, due to repairs, the water was cut off in the village where Zenyk and Marichka were staying. Mrs. Tarnavska is in despair! How can she fill the hot tub for her dear guests? And how can the other villagers live without water?

Fortunately, Zenyk used to work as the director of the water utility, and Marichka — as a logistics manager. Zenyk suggested that they deliver the water using Mrs. Tarnavska’s cars (whose cars did you think?). The idea came from Zenyk, the cars from Mrs. Tarnavska, and the process management from Marichka.

There is one street in the village. Let’s represent the street as a coordinate line.

On this line, there are \(n\) houses located at points with coordinates \(h_i\) kilometers. The water demand of the \(i\)-th house is \(a_i\) liters of water.

There are also \(m\) stations with an infinite supply of water, located at points with coordinates \(s_i\) kilometers. At each station, there is a car with a tank of capacity \(k\) liters, which can load water at this station and deliver it to the houses. A car can load as much water as it wants (no more than fits in the tank) as many times as it wants only at its own station. Water can be brought to any house from any station. After delivery, each car must return to its station.

Marichka needs to minimize the total distance traveled by the cars to cover the residents’ needs and return to their stations. She hasn’t worked in logistics for a long time and forgot what to do.

Help Marichka — find the minimum total distance the cars will travel.

Input

The first line contains three integers \(n\), \(m\), \(k\) — the number of houses, the number of stations, and the tank capacity of each car in liters.

The next \(n\) lines contain two integers \(h_i\) and \(a_i\) — the coordinate in kilometers of the corresponding house and the water demand in liters of the residents of this house.

The next line contains \(m\) integers \(s_i\) — the coordinates in kilometers of the water stations.

Output

In a single line, print an integer — the minimum total distance in kilometers that the cars must travel to deliver water to the houses and return to their stations.

Constraints

\(1 \le n, m \le 10^3\),

\(1 \le k, a_i \le 10^9\),

\(0 \le h_i, s_i \le 10^6\),

\(h_i < h_{i+1}\),

\(s_i < s_{i+1}\).

10 points:

\(1 \le n, m \le 100\),

\(1 \le k, a_i \le 100\),

\(0 \le h_i, s_i \le 10^3\);

15 points: without additional constraints.

Samples

Input (stdin) сopy	Output (stdout) сopy
9 2 6 4 4 7 4 11 1 13 1 20 10 27 1 29 1 30 47 47 47 10 30	334

Notes

• The car from the first station carries 4 liters of water to the first house and returns to the station. The distance from the station to the house is 6 km. The car covers it in both directions, so it will travel 12 km.

• From the first station, it carries 4 liters to the second house and returns to the station — travels 6 km.

• From the first station, 1 liter to the third house — travels 2 km.

• From the first station, 1 liter to the fourth house, 5 liters to the fifth house — 20 km.

• From the second station, 1 liter to the sixth house, 5 liters to the fifth house — 20 km.

• From the second station, 1 liter to the seventh house — 2 km.

• The needs of the eighth house can be met with water from the second station by traveling 0 km.

• To satisfy the needs of the ninth house, the car from the second station must make 8 trips of 34 km. \(8 \cdot 34 = 272\) (km).

\(12+6+2+20+20+2+0+272=334\) (km).