Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PERNALTY - Dragon Football

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/pernalty


Dragon football là một loại hình thể thao của các kỵ sĩ rồng. Cũng giống như bóng đá, sau 2 hiệp chính và 2 hiệp phụ nếu vẫn không phân định được thắng thua, 2 đội phải thực hiện những loạt sút luân lưu. Luật sút luân lưu như sau. Mỗi đội có (S+1) cầu thủ trong đó có 1 thủ môn, khung thành có dạng một dải (1xN) với các ô được đánh số từ trái qua phải. Mỗi đội chỉ có một lượt sút duy nhất theo quy tắc:
_ Thủ môn duy nhất của đội phòng thủ phải chọi với S cầu thủ của đội tấn công.
_ Mỗi cầu thủ phải chọn 1 vị trí để đứng, chỉ được sút bóng trên đường thẳng vuông góc với xà ngang của khung thành.
_ Vị trí của cầu thủ đước định nghĩa bằng 2 thống số: T và X. Với T là khoảng cách của cầu thủ so với khung thành và X là tọa độ mà bóng sẽ đến khung thành.
_ Khi tiếng còi cất lên, tất cả cầu thủ đồng loạt sút quả bóng của mình vào khung thành với vận tốc như nhau, một cầu thủ đứng cách khung thành T mét thì quả bóng của cầu thủ đó sẽ mất T giây để đến khung thành.
_ Với sức mạnh của rồng, thủ môn có thể di chuyển tối đa K ô trong 1 giây và có thể cản phá nhiều cú sút một lúc nếu anh đang đứng ở đúng vị trí và đúng thời điểm các quả bóng bay đến khung thành.

Khung thành được tô màu xanh lá cây, các điểm tô màu xanh dương chính là vị trí các cầu thủ (chú ý là có thể có nhiều cầu thủ đứng cùng một vị trí). Trục thẳng đứng biểu diễn khoảng cách của cầu thủ so với khung thành, ví dụ từ trái sang thì
_ cầu thủ 1: cách khung thành 1m và sẽ sút bóng vào vị trí 1
_ cầu thủ 2: cách khung thành 2m và sẽ sút bóng vào vị trí 2
_ cầu thủ 3: cách khung thành 3m và sẽ sút bóng vào vị trí 5…
Tên chúa tể ác độc Galbatorix đang nắm giữ một đội bóng hùng mạnh, nhưng Neo vừa thu phục được một con rồng con và đc giao vị trí thủ môn. Một kỵ sĩ còn ít kinh nghiệm và một con rồng non nớt phải chiến đấu với cả một đội bóng. Hãy giúp Neo chọn vị trí ban đầu và cách di chuyển để đấm đc càng nhiều bóng ra khỏi khung thành càng tốt.

Input

_ Dòng đầu tiên là 3 số N, K, S (1<= N <=10000; 0<= K <=N; S<=100 000) lần lượt là kích thước khung thành, số ô tối đa mà thủ môn có thể di chuyển trong 1 giây và số lượng cầu thủ sút bóng.
_ S dòng tiếp theo biểu diễn thông tin về vị trí các cầu thủ, dòng thứ i chứa 2 số T_i và X_i (với T_i là khoảng cách từ cầu thủ đó đến khung thành còn X_i là vị trí được đánh số trên khung thành mà cầu thủ đó sẽ sút vào). (1<= X_i <=N và 1<= T_i <=100)

Output

_ Một dòng duy nhất chứa số lượng bóng lớn nhất mà Neo có thể đấm ra đc.

Example

Input:
10 2 7
1 1
2 2
3 5
5 7
6 10
6 10
6 10


Output:
5

Giải thích test vd: Ban đầu thủ môn đứng ở vị trí 1, 1s sau thì bắt trái bóng ở đó, giây tiếp theo di chuyển qua trái 1 bước đến vị trí số 2 rồi bắt ngay trái bóng ở vị trí 2, sau đó 4s tiếp theo mỗi giây di chuyển 2 bước sang phải thì vừa kịp bắt 3 trái bóng ở vị trí 10
"PERNALTY", chữ R bị thừa là viết tắt của DRAGON =))


Được gửi lên bởi:sieunhan
Ngày:2009-04-23
Thời gian chạy:0.400s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:duyhung123abc

hide comments
2016-08-08 15:08:50
nhầm min thành max mất 1 hit -_- ko còn gì nhọ hơn
2015-03-08 13:19:09 I have LASER BEAMS !
@trandatbav : Đenđi xin nêu tên :)) 0.18s
2012-01-04 15:25:15 trandatbav
Mấy bác cứ chém gió, đồng chí nào chạy dc 0.5 với 0.25s nêu tên cái nào
2012-01-04 03:49:58 Siêu Nhân Trong Suốt
0.25s đc ko anh . cho cái thằng to mồm phía dưới hết AC
2012-01-04 03:49:48 Siêu Nhân Trong Suốt
http://vn.spoj.pl/problems/PERNALTY/
2012-01-04 03:46:47 Any fool will do
Cho thêm 0.5 giây nữa đi PS ơi ! Làm mãi mà không AC được :((

Last edit: 2012-01-05 03:10:34
2012-01-03 23:16:53 Tmbao
Time limit chặt quá :(

Last edit: 2012-01-04 03:49:16
2011-12-29 15:39:17 trandatbav
Làm bài này rồi mới biết sự nguy hiểm ở đời là những cái mình nắm bắt nhưng lại ngu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.