Dragon Football

View as PDF

Submit solution


Points: 0.81 (partial)
Time limit: 0.6s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
duyhung123abc
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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 ~(1\times N)~ 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.

image

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 \le N \le 10000~; ~0 \le K \le N~; ~S \le 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 \le X\_i \le N~ và ~1 \le T_i \le 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.

Sample Input

10 2 7
1 1
2 2
3 5
5 7
6 10
6 10
6 10

Sample Output

5

Note

Ban đầu thủ môn đứng ở vị trí ~1~, 1s sau thì bắt trái bóng ở đó.

Giây tiếp theo thủ môn 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~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.