Unknown to some, Rar the Cat is greedy and has an unknown secret of eating ikan bilis (tiny fishes) while walking home from school. The journey from his home to school is X metres and there are N stalls that sell ikan bilis along the way.
Stores selling ikan bilis are situated at different positions and sell ikan bilis at different prices. It is noted that the ith store is located at Di metres away from his school and sells ikan bilis at Ci per fish. Stores have large stockpiles and thus can be assumed to have an infinite amount of ikan bilis up for sale.
It is noted that he has to eat exactly 1 ikan bili for every metre he walks, if not he would have a sad journey home. To clarify, lets say Rar is currently at 3 metres away from his school and there is an ikan bilis store. Rar will eat the third ikan bili before purchasing anything from the store at 3 metres away from his school.
It is guaranteed that his school canteen also sells ikan bilis and this will be denoted by a store at 0m. He would only eat the first ikan bilis when he reaches 1 metre away from the school. He will also eat an ikan bilis at the Xth metre, when he has just arrived home
However, since his pockets are not very huge, Rar the Cat can only hold up to K ikan bilis at any point in time. With these, he wants to know whether he would have a sad journey home. If he is able to not have a sad journey home, he wants to know the minimum amount of money required to buy ikan bilis such that he does not have a sad journey home.
The first line of input will contain 3 integers, X, K and N.
Subsequent N lines will contain 2 integers each, with row i containing Di and Ci for the ith store. These are not provided in any order.
If Rar the Cat is forced to have a sad journey home, print a single integer -1.
If he is able to not have a sad journey home, print the minimum cost required to do so.
Unless otherwise specified, 1 ≤ X, K ≤ 1,000,000,000 and 1 ≤ N ≤ 1,000,000
Since ikan bilis are cheap, the cost of each ikan bilis will not exceed 1,000.
There will not be more than one store at each metre away from school. (ie. There will not be 2 stores that share the same distance away from Rar the Cat's school). There will also not be a store at Rar the Cat's house. However, there will always be a store at Rar the Cat's school (0 metres away).
Subtask 1 (9 points): N = 1
Subtask 2 (23 points): 1 ≤ N = X = K ≤ 100,000
Subtask 3 (32 points): 1 ≤ N ≤ X ≤ 1,000,000
Subtask 4 (36 points): No further restrictions.
Subtask 5 (0 points): Sample Testcases
Sample Input 1
10 10 1
Sample Output 1
Explanation for Sample Testcase 1
There is only one stall that sells ikan bilis, his school. To prevent himself from having a sad journey home, he will need to buy at least 10 ikan bilis. Since his pockets can hold up to 10 ikan bilis, he can simply buy them all from school, costing $2 per ikan bilis for a total of $20.
Sample Input 2
10 5 1
Sample Output 2
Explanation for Sample Testcase 2
There is only one stall that sells ikan bilis, his school. To prevent himself from having a sad journey home, he will need to buy at least 10 ikan bilis. Since his pockets can only hold up to 5 ikan bilis, he will definitely have a sad jouney home.
Sample Input 3
10 6 2
Sample Output 3
Explanation for Sample Testcase 3
Rar the Cat can buy 6 ikan bilis from school, this will last him from 0m to 6m. This is the maximum his pockets can hold. He needs to buy a further 4 more ikan bilis at the store at position 5, at the cost of $2 per ikan bilis. This is to ensure that he has enough ikan bilis to last him through the daunting journey home.