Problem : 66 - Farmer John

Problem Statistics

Solved Member: 24　　Submission: 121　　User Tried: 24

Statement:

農夫約翰有一塊 n * m 農地，每行都會有一條連續的橫條被草覆蓋，瀚瀚國國王為了獎賞勤勞的農夫約翰，決定從草皮上面割出一塊 x * y 的矩形，在上面放滿黃金，再送他一個美女，農夫約翰高興得跳了起來，但此時瀚瀚國國王卻撥了他一頭冷水說，你要先告訴我有幾種割法，我才送你一個美女，苦惱的農夫痴漢將頭轉向了你，你能否幫他解決問題呢？

Input:Output:

第一行有四個整數n m x y(1 <= n, m, x, y <= 5000000)
接下來有m行，每行兩個數字Si Li (1 <= Si <= n, 0 <= Li <= n, Si + Li <= n+1 )，代表第i行的草的開頭位置與長度。

請輸出唯一的數字，代表你覺得可能是答案的答案。

Sample Input:Sample Output:

5 6 2 3
1 5
1 3
1 2
1 1
3 3
2 4

HINT:

範測的圖

Source:

PA 2006 Round 4

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	131068kb
1-1	1000ms	131068kb	10
1-2	1000ms	131068kb
1-3	1000ms	131068kb
2-1	1000ms	131068kb	10
2-2	1000ms	131068kb
2-3	1000ms	131068kb
2-4	1000ms	131068kb
3	1000ms	131068kb	10
4	1000ms	131068kb	10
5-1	1000ms	131068kb	10
5-2	1000ms	131068kb
6	1500ms	131068kb	10
7	2500ms	131068kb	10
8	6000ms	131068kb	10
9	10000ms	131068kb	10
10-1	13000ms	131068kb	10
10-2	1000ms	131068kb