To Fish or Not to Fish

The owners of a fishing vessel working the Kama River decided to optimize their business for the summer season.

They obtained a seasonal permit to fish at $n$ points along the river at distances $x_1, x_2, \ldots, x_n$ kilometers from the mouth. At point number $i$, at most $a_i$ tons of fish may be caught.

The fish caught can be sold at $m$ wholesale bases located along the river bank at distances $y_1, y_2, \ldots, y_m$ kilometers from the mouth. The base at point number $j$ is willing to buy at most $b_j$ tons of fish this season at a price of $c_j$ rubles per ton.

Distances from the mouth to the fishing points and wholesale bases are measured along the river channel.

The vessel sets out to fish from the river mouth and must return there after the season ends. During the season, the vessel may travel freely up and down the river, stopping to fish or to sell fish. The vessel's carrying capacity is sufficient to transport any amount of caught fish. When moving away from the mouth, the vessel travels against the current and spends fuel worth $p$ rubles per kilometer. When moving toward the mouth, the vessel travels with the current and therefore spends no fuel.

At the end of the season, the profit from the catch equals the total value of the fish sold minus the total cost of the fuel spent.

Write a program that determines the maximum profit that can be obtained during the season.

The first line of the input contains three integers $n$, $m$, and $p$: the number of fishing points, the number of wholesale bases, and the fuel price ($1 \le n, m \le 500\,000$; $0 \le p \le 10^9$).

The next $n$ lines contain two integers each, $x_i$ and $a_i$: the distance from the mouth and the maximum catch for each fishing point ($0 < x_1 < x_2 < \ldots < x_n \le 10^9$; $0 < a_i \le 10^6$).

The next $m$ lines contain three integers each, $y_j$, $b_j$, and $c_j$: the distance from the mouth, the maximum amount of fish bought in tons, and the purchase price per ton for each wholesale base ($0 < y_1 < y_2 < \ldots < y_m \le 10^9$; $0 < b_j, c_j \le 10^6$).

The output must contain a single integer: the maximum possible profit.

In the second example, the following actions are optimal. The vessel should reach the point at a distance of 6 kilometers from the mouth, spending 600 rubles on fuel, and catch 5 tons of fish there. After that, it should go 1 kilometer down the river to the base at a distance of 5 kilometers from the mouth and sell the caught fish at a price of 2000 rubles per ton. Then it should return to the river mouth. The total profit will be 9400 rubles.