Difficulity：
N/A
| Test Data Sets: 1 (Hidden) | Judging:
Traditional Judge

Accepted : 2 Times | Submit :74 Times | Clicks : 556

Accepted ： 2 Users | Submit : 3 Users | Accepted rate : 67%

Time Limit ：3000 ms | Memory Limit : 64000 KBytes

Update : 2012-10-29 17:20

Accepted : 2 Times | Submit :74 Times | Clicks : 556

Accepted ： 2 Users | Submit : 3 Users | Accepted rate : 67%

Time Limit ：3000 ms | Memory Limit : 64000 KBytes

Update : 2012-10-29 17:20

Temmo have N sticks to cut. All of the sticks are placed parallel with the axis. The left side of the i-th stick is at the coordinate li, and the right side of that is at the coordinate r_{i}. For convenience you can treat these sticks as segments.

Temmo needs to make C cuts. The coordinate of each cut c_{i} must be integer, and between the left most coordinate of l_{i} and the right most coordinate of r_{i} (inclusive). And the distance between each pair of cuts must not be less than G. He wants to make the work easier, so he wants to cut the least sticks in these C cuts. The i-th stick is cut by the j-th cut if l_{i} ≤ c_{j} ≤ r_{i}. Denote wi as the number of sticks would be cut in the i-th cut, can you tell him the minimum sum of all w_{i}?

- 1 ≤ N ≤ 10
^{4} - 1 ≤ G,C ≤ 10
- 1 ≤ l
_{i}, r_{i}≤ 2^{12} - All of the numbers are integers.

**
Input：**

There are at most 100 test cases in the input. Each test case starts with

three numbers N, G, C in a line. Then followed by N lines, each of these

lines contains two numbers l_{i} and r_{i}.

**
Output：**

For each test case output the minimum sum of w_{i}.

**
Sample Input：**

若題目沒有特別說明，則應該以多測資的方式讀取，若不知如何讀取請參考 a001 的範例程式。

3 1 2 2 5 3 6 7 9

**
Sample Output
：**

2

**
Hint
：**

**
Author
：**

C |
C++ |
JAVA |
PASCAL |
---|---|---|---|

50828. rabbit125 (352ms, 916KB, 1739B) |
|||

Program running time may be affected by various factors. Check server system environment information here