Một nhóm nhà thám hiểm đi tìm kho báu. Kho báu được cất giấu ở phòng bên phải nhất của tầng dưới cùng trong một hầm (có ~M~ tầng được đánh số từ ~1~ đến ~M~ theo thứ tự từ trên xuố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á. Mỗi phòng có cửa xuống phòng ngay phía dưới và có cửa sang phòng kế bên. Từ trên mặt đất có ~N~ cửa xuống phòng tầng ~1~. 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 một khoảng thời gian khác nhau.

Yêu cầu

Bạn hãy chỉ đường cho nhóm nhà thám hiểm để đi từ mặt đất xuống phòng chứa kho báu một cách nhanh nhất để lấy được kho báu.

Dữ liệu vào

• Dòng ~1~ ghi ~M~ và ~N~ ~(1 ≤ M ≤ 2222, 1 ≤ N ≤ 10)~;
• Từ dòng ~2~ đến dòng ~2M + 1~: dòng chẵn ghi ~N~ số là khoảng thời gian phá các cửa từ trên xuống, dòng lẻ ghi ~N – 1~ số là khoảng thời gian để phá các cửa ngăn giữa các phòng cùng tầng.
  Lưu ý: 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.

Kết quả ra

Một con số duy nhất là khoảng thời gian nhỏ nhất để nhóm nhà thám hiểm đến phòng chứa kho báu.

Sample Input

4 2
99 10
1
10 99
1
99 10
1
10 99
1

Sample Output

44