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.|

ROBOCON - VOI 2012 Robocon

Cuộc thi vòng loại Robocon năm nay có chủ đề "Gặp gỡ". Các Robot sẽ tranh tài trên một lưới ô vuông gồm n hàng n cột. Các hàng của lưới được đánh số từ 1 đến n, từ trên xuống dưới. Các cột của lưới được đánh số từ 1 đến n, từ trái sang phải. Trên k ô vuông của lưới có đặt chướng ngại vật. Ở phần thi Robot tự động, mỗi đội sẽ phải sử dụng đồng thời hai con Robot.

Tại thời điểm xuất phát, Robot thứ nhất được đặt tại ô (1,1), mỗi bước chỉ được phép di chuyển sang ô kề cạnh bên phải, hoặc xuống ô kề cạnh bên dưới hoặc xuống ô kề đỉnh phía dưới bên phải.

Robot thứ hai được đặt tại ô (1,n), mỗi bước chỉ được phép di chuyển sang ô kề cạnh bên trái hoặc xuống ô kề cạnh bên dưới hoặc xuống ô kề đỉnh phía dưới bên trái.

Bắt đầu từ thời điểm xuất phát được tính là 0, hai Robot phải di chuyển liên tục theo qui tắc đã nêu. Thời gian di chuyển từ một ô sang ô kế tiếp được tính là 1 giây. Nhiệm vụ của đội chơi là phải lập trình điều khiển hai Robot xuất phát cùng lúc, di chuyển tránh chướng ngại vật để gặp nhau tại một ô vuông không có chướng ngại vật. Hai Robot gặp nhau càng sớm đội chơi càng được nhiều điểm. Lưới ô vuông được thiết kế đảm bảo là luôn có cách đi để hai Robot gặp được nhau.

Yêu cầu: Hãy tìm cách điều khiển sao cho hai Robot gặp nhau ở thời điểm sớm nhất.

Ràng buộc: 50% số tests ứng với 50% số điểm của bài có n ≤ 100.

Input

  • Dòng thứ nhất chứa hai số nguyên dương n, k (n ≤ 500, k ≤ 10000).
  • Dòng thứ i trong số k dòng tiếp theo chứa 2 số nguyên dương ui, vi tương ứng là tọa độ hàng và cột của ô có đặt chướng ngại vật (i = 1, 2, ..., k).

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Ghi ra một số nguyên dương là thời điểm sớm nhất tìm được.

Example

Input:
5 5
2 2
1 4
2 3
3 5
4 2 Output: 3

Được gửi lên bởi:VOJ Team
Ngày:2012-01-18
Thời gian chạy:1s
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ừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOI 2012

hide comments
2018-05-08 11:44:57
.
2018-05-08 11:43:36
Học sinh cô Hương em trai anh Mạnh
Tự tin AC chạy trâu .
_Tuấn nhi đồng
2017-12-09 10:17:12
45 - > 60 - > 75 @@
frostpixel aka.How 2 AC
2017-11-22 06:18:34
loang khó v

Last edit: 2017-11-22 06:18:49
2017-07-24 06:19:12
kham khảo lời giải tại https://vietcodes.github.io/code/24

Last edit: 2017-08-06 10:57:37
2017-07-05 15:57:57
qhd AC
2017-01-03 15:16:25
Đọc nhầm đề loang bình thường mà cũng 45đ =)))
2017-01-02 04:07:09
qhđ AC, cơ mà chú ý số bước có thể lớn hơn n
2016-11-28 13:09:53 df
Loang AC
2016-11-25 10:51:50
yay đc boss Hưng support chắc AC
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.