ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural FU Open Personal Contest 2014

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Bolero

Time limit: 1.0 second
Memory limit: 64 MB
Winter in Yekaterinburg is the longest time of the year. And everyone spends long winter evenings in his own way. Denis is a big fan of classical music, at least twice a week he attends concerts at the Philharmonic.
This year, Denis wants to buy tickets for the whole season at once and even already has chosen a list of concerts, which he wants to attend. Now, he thinks, how to buy tickets. There is an opportunity in the Philharmonic to choose any k or more concerts and to buy a single subscription for all of them. The cost of this subscription will be equal to the total cost of all concerts in it but with a discount p percent. There are many types of such subscriptions, with different k and p. In addition, for some concerts Denis, as a student, has a discount. This discount is valid only if he buys the ticket separately, outside the subscription.
Denis, like any other poor student, wants to attend all the concerts, spending as little money as possible. However, he knows that there are always more people wanting to attend a concert than the number of seats in the Philharmonic hall. So he will not buy more than one ticket for one concert (separately or in a subscription), even if it allows him to save money.

Input

The first line contains integers n and m that are the number of concerts Denis wants to attend, and a number of different subscription types at the Philharmonic (2 ≤ n ≤ 105; 1 ≤ m ≤ 105). The i-th of the following n lines contains integers si and di that are the price of a ticket and the discount for students in percent at the i-th concert (100 ≤ si ≤ 50 000; 0 ≤ di ≤ 100). The j-th of the following m lines contains integers kj and pj that are the minimum number of concerts that can be combined in the subscription of the j-th type, and a discount for it in percent (2 ≤ kjn; 1 ≤ pj ≤ 100).

Output

Output the minimum amount of money Denis has to spend to attend all the concerts. The answer should be given with an absolute or relative error not exceeding 10−6.

Sample

inputoutput
6 2
500 0
700 0
300 0
400 0
500 50
800 0
5 10
6 15
2680.00

Notes

In the example, Denis needs to buy a subscription of the first type (with 10% discount) for all concerts, except the fifth one, and to buy a ticket for the fifth concert with a student discount of 50%.
Problem Author: Denis Dublennykh
Problem Source: Open Ural FU Personal Contest 2014
To submit the solution for this problem go to the Problem set: 2092. Bolero