Đảo giấu vàng

View as PDF

Submit solution


Points: 0.33 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Polish Olympiad in Informatics
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

1 nhà thám hiểm nọ vừa phát hiện ra một bản đồ kho báu. Trên bản đồ miêu tả 1 hòn đảo nằm ở nam Thái Bình Dương. Trên hòn đảo có ~N~ vị trí có kho báu là các mỏ vàng. Để được phép khai thác nhà thám hiểm quyết định dốc hết tiền của ra mua 1 mảnh đất và khai thác các mỏ vàng trên đó. Tuy nhiên Nhà thám hiểm cũng không giàu có gì lắm nên chỉ có thể mua được 1 miếng đất hình chữ nhật có kích thước tối đa là ~S \times W~ và theo yêu cầu của Chúa Đảo thì miếng đất phải song song với 2 trục ~Ox~ và ~Oy~ để không làm mất mỹ quan của hòn đảo (các mỏ vàng nằm trên đường biên của miếng đất cũng sẽ được quyền khai thác). Bạn hãy lập trình giúp Nhà thám hiểm tính xem ông ta có thể chiếm được nhiều nhất là bao nhiêu mỏ vàng.

Lưu ý: Bài này nếu không cẩn thận sẽ rất dễ bị ngộ nhận. Vì vậy nên phải đặc biệt chú ý. Là 1 bài khó vì thế nên sau một thời gian sẽ để cho các bạn có thể xem lời giải và download test.

Input

Dòng 1: 2 số nguyên dương ~S~ ~W~ ~(1 \leq S, W \leq 10000)~. ~S~ là độ dài cạnh song song với trục ~Ox~. ~W~ là độ dài cạnh song song với trục ~Oy~.

Dòng 2: số nguyên dương ~N~ ~(1 \leq N \leq 15000)~.

~N~ dòng tiếp theo, dòng thứ ~i~ mô tả vị trí của mỏ vàng thứ ~i~ là 2 số nguyên ~x_i~ và ~y_i~. ~(-30000 \leq x_i, y_i \leq 30000)~.

Output

Gồm 1 dòng duy nhất ghi ra số lượng nhiều nhất mỏ vàng mà Nhà thám hiểm có thể có được .

Sample Input

1 2
12
0 0
1 1
2 2
3 3
4 5
5 5
4 2
1 4
0 5
5 0
2 3
3 2

Sample Output

4

Note

Download test và solution tại đây.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.