Aloha is a poor guy who likes riding a bike. But he is too poor to afford a bicycle.

Recently, the Boom's bike-sharing service entered his school. It only costs yuan for every single rent of a bicycle. From then on, Aloha could rent a bike and enjoy the speed and passion of riding.

The Boom's company has launched a promotion program named the . In this program, users can buy discount cards with several free rents and a valid period. For example, after purchasing a discount card with free rents and days of valid time, one doesn't need to pay extra fees for the following rents in the next days. Note that, no matter when the card is bought on day , it will always expire at the end of day . Also, any new discount card overrides the previous one even if it is still valid, i.e., the remaining free rents of the previous discount card are voided immediately when the new discount card is purchased.

There are different types of discount cards in the . A card of th type with free rents and a valid period of days costs yuan. One can buy any type of discount card unlimited times.

Given the rental records, Aloha wants to know the minimum money he has to pay, provided that he takes the best strategy.

输入描述:

The first line of input contains three integers  , denoting the number of discount card types, the number of rental records, and the price of a single rent.
Then follow  lines, specifying the  types of discount cards. The th line contains three integers  , denoting the valid period, the number of free rents, and the price of a discount card of type .
The last  lines describe Aloha's rental records. The th of them contains two integers  , representing that Aloha would rent bikes  times on Day . It is guaranteed that  are distinct.

输出描述:

Print one integer in a line, denoting the minimum money Aloha has to pay if he adopts the best strategy.

2 1 10
1 3 12
1 2 9
1 10

42

2 4 10
1 3 12
1 2 9
1 3
2 3
3 3
4 1

45