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

HYBINLADEN - Truy bắt BINLADEN

Trùm khủng bố Bin Laden trốn trong 1 căn hầm được đào sâu xuống mặt đất M tầng, mỗi tầng có N phòng. Các phòng được ngăn cách bằng các cửa rất khó phá. Các phòng có cửa xuống phòng ngay phía dưới và 2 phòng ở 2 bên. Từ trên mặt đất có N cửa xuống N phòng tầng -1. Bin Laden ở tầng dưới cùng (tầng -M) phòng thứ N (phòng ở bên phải nhất). Mỗi cửa được làm bằng một kim loại khác nhau với độ dày khác nhau nên việc phá cửa cần thời gian khác nhau.

Bạn hãy tìm cách đi từ mặt đất xuống phòng của Bin Laden nhanh nhất không hắn thoát mất.

Dữ liệu:

  • Dòng 1 ghi M và N (1 ≤ M ≤ 2222; 1 ≤ N ≤ 10)
  • Dòng 2 đến 2M + 1, dòng chẵn ghi N số, dòng lẻ ghi N - 1 số là chi phí để phá cửa (chi phí thuộc đoạn [0..1000].

Kết quả:

  • Ghi ra 1 số là thời gian nhỏ nhất để đến được phòng của Bin Laden

Ví dụ:

Input:
4 2
99 10
1
10 99
1
99 10
1
10 99
1
Output:
44

Giải thích: Đi theo đường zigzag

+--99--+--10--+

|      |      |

|      1      |

|      |      |

+--10--+--99--+

|      |      |

|      1      |

|      |      |

+--99--+--10--+

|      |      |

|      1      |

|      |      |

+--10--+--99--+

|      |      |

|      1      |

|      |      |

+------+------+


Được gửi lên bởi:noname00.pas
Ngày:2017-11-08
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C-CLANG C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PAS-FPC PYTHON PYTHON3
Nguồn bài:Bài tập thực hành CSL (Hiếu HY)

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.