Vương quốc IOI có lãnh thổ được biểu diễn bằng một lưới vuông gồm \(L\) hàng và \(L\) cột. Các hàng được đánh số từ \(1\) đến \(L\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(L\) từ trái sang phải. Ô ở hàng \(i\), cột \(j\) được ký hiệu là \((i,j)\).

Gần đây, dịch bệnh lan rộng khiến nhu cầu chăm sóc y tế trong vương quốc tăng cao. Vì vậy, quốc vương Bitaro quyết định xây bệnh viện tại bốn ô ở góc lưới: \((1,1)\), \((1,L)\), \((L,1)\) và \((L,L)\). Mỗi bệnh viện được trang bị một xe cứu thương.

Bitaro thận trọng nên muốn mô phỏng tình huống có bệnh nhân cần được cứu giúp. Trong kịch bản của ông, tại thời điểm \(0\), có \(N\) bệnh nhân gửi yêu cầu cứu giúp. Bệnh nhân thứ \(k\) (\(1 \le k \le N\)) ở ô \((X_k,Y_k)\). Ông muốn biết liệu có thể đưa tất cả bệnh nhân đến một trong các bệnh viện không muộn hơn thời điểm \(T\) hay không.

Các xe cứu thương vận chuyển bệnh nhân theo những quy tắc sau:

• Mỗi xe có thể bắt đầu di chuyển từ thời điểm \(0\) trở đi. Xe lặp lại việc xuất phát từ bệnh viện của mình, đi đến ô có bệnh nhân, đón bệnh nhân, rồi quay về bệnh viện đó để trả bệnh nhân. Xe có thể không thực hiện chuyến nào.
• Mỗi xe chở được nhiều nhất một bệnh nhân tại một thời điểm.
• Mỗi xe chỉ được đưa bệnh nhân đến bệnh viện nơi xe được bố trí ban đầu. Không được cho bệnh nhân xuống xe tại ô không có bệnh viện.
• Mỗi lần di chuyển sang một ô kề trên, dưới, trái hoặc phải mất một đơn vị thời gian. Thời gian đón và trả bệnh nhân có thể bỏ qua.
• Các xe thuộc những bệnh viện khác nhau được phép ở cùng một ô tại cùng một thời điểm.

Bitaro không tự xác định được kết quả của kịch bản này nên nhờ bạn giúp. Cho kích thước lãnh thổ và thông tin về kịch bản, hãy xác định có thể đưa tất cả bệnh nhân đến bệnh viện không muộn hơn thời điểm \(T\) hay không.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(L,N,T\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(k\) chứa hai số nguyên \(X_k,Y_k\).

Các số trên cùng một dòng được ngăn cách bởi dấu cách.

Dữ liệu ra

In một dòng chứa Yes nếu có thể đưa tất cả bệnh nhân đến bệnh viện không muộn hơn thời điểm \(T\); nếu không, in No.

Ràng buộc

• \(3 \le L \le 10000\).
• \(1 \le N \le 160\).
• \(1 \le T \le 20000\).
• \(1 \le X_k \le L\) và \(1 \le Y_k \le L\) với mọi \(1 \le k \le N\).
• \((X_k,Y_k)\) không trùng với bất kỳ ô nào trong bốn ô \((1,1)\), \((1,L)\), \((L,1)\), \((L,L)\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(4\) điểm: \(T \le 50\).
2. \(8\) điểm: \(T \le 160\).
3. \(5\) điểm: \(N \le 10\).
4. \(18\) điểm: \(N \le 20\).
5. \(15\) điểm: \(N \le 45\), \(L\) là số lẻ và \(Y_k=\frac{L+1}{2}\) với mọi \(1 \le k \le N\).
6. \(31\) điểm: \(N \le 45\).
7. \(19\) điểm: Không có ràng buộc bổ sung.

Ví dụ

6 4 8
1 3
2 2
3 4
5 5

Yes

9 5 19
5 5
5 5
7 5
2 5
9 5

No

7 7 16
6 1
2 4
4 5
5 5
3 4
6 4
5 1

Yes

200 15 800
126 45
196 40
43 58
96 13
28 33
44 55
60 22
58 156
135 183
44 29
92 182
157 138
30 132
175 87
166 57

No

Giới hạn

Giới hạn thời gian là \(2\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh và tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ hai. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.