Đảo giấu vàng

Xem PDF

Điểm: 350 (p) Thời gian: 0.38s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Đề bài: \(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\) x \(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\)\(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.

Input

  • Dòng 1: \(2\) số nguyên dương \(S,W\). \((1 \le S,W \le 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 \le N \le 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\)\(y_i\) \((-30000 \le x_i,y_i \le 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.

Example

Test 1

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
Output
4

Bình luận