With Halloween coming up in ~N~ days, you realized that you need to buy costumes! Specifically, you want to buy ~M~ different costumes before Halloween so that you have multiple options to choose from on Halloween. Thankfully there is a store nearby that allows you to buy at most one costume a day, however the price of the costume keeps changing. Initially, the costumes will cost ~$1\,000\,000~, however over the course of ~N~ days, they will change ~Q~ different times. You will be given this list of changes beforehand which will tell you that at some moment on the ~d_i^{th}~ day before Halloween, the price of buying a costume changes to ~p_i~. The list will be in the order that the changes occurred. Can you determine the minimum cost to buy all ~M~ costumes?

Note that the price of a costume may change multiple times during a given day, and you can choose what time you will enter the store to buy the costume. In addition, the store will open the next day with the costumes having the exact price that it closed at the previous day (a price change will not happen overnight, nor at the moment the store opens or closes).

Constraints

~1 \le M \le N \le 10^{12}~
~1 \le Q \le 200\,000~
~1 \le d_i \le N~ for ~1 \le i \le Q~
~1 \le p_i \le 1\,000\,000~ for ~1 \le i \le Q~
~d_{i-1} \ge d_i~ for ~2 \le i \le Q~

Input Specification

The first line of input contains ~3~ integers, ~N, M, Q~.

The next ~Q~ lines describe the changes in the price of a costume, listed in the order that the changes occurred. Each line contains ~2~ integers, ~d_i, p_i~. This indicates that on the ~d_i^{th}~ day before Halloween, the price of buying a costume changes to ~p_i~.

Note that a 64-bit integer may need to be used to store ~N~ and ~M~. In C++, this can be done with long long. In Java, this can be done with long. In Python, the standard int will suffice.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output a single integer, the minimum cost to buy ~M~ costumes, before Halloween, given that you can buy at most one costume a day. Note that this answer may not necessarily fit in a 32-bit integer.

Sample Input

7 3 6
6 10
4 1
3 5
2 8
2 2
2 7

Sample Output

4

Sample Explanation

You can buy a costume ~4~ days before Halloween right after the price changes to ~$1~. You can then buy a costume ~3~ days before Halloween for ~$1~ right when the store opens, and buy a costume ~2~ days before Halloween right after the price changes to ~$2~.