Tên khủng bố Osama bin Laden trước khi bị giết đã đào một con hầm sâu xuống lòng đất nhằm lẩn trốn sự truy đuổi của các lực lượng biệt kích Hoa Kỳ. Con hầm này gồm M tầng (đánh số từ 1 đến M, tầng 0 và tầng M + 1 lần lượt là lối vào và lối ra), mỗi tầng có N căn phòng (đánh số từ 1 đến N). Một căn phòng có các cánh cửa ở phía dưới, cửa của 2 phòng ở 2 bên. Từ trên mặt đất có N cửa xuống, cửa ra cũng bao gồm có N cửa. Osama bin Laden lúc đó đang ở phòng N của tầng M + 1. Vì biết mình là một tên khủng bố, Osama bin Laden luôn cẩn thận xây dụng các cánh cửa thật kiên cố và chắc chắn để mình có thể an toàn. Nhưng vì nghèo, mỗi cánh cửa được làm từ các loại nguyên liệu khác nhau nhằm vừa đủ số tiền mà hắn đang có, vì vậy thời gian để phá các cảnh cửa là khác nhau.

Lực lượng biệt kích Hoa Kỳ đã xác định được vị trí con hầm mà Osama bin Laden đang lẩn trốn, tuy nhiên không biết cách làm thế nào để xuống chỗ của Osama bin Laden một cách nhanh nhất, nếu xuống chậm, hắn có thể chạy thoát. Bạn hãy giúp lực lượng biệt kích Hoa Kỳ tiêu diệt hắn!!!

INPUT:

Dòng đầu tiên gồm 2 số nguyên dương M và N.

Dòng thứ hai đến 2M + 1, dòng chẵn gồm N số, dòng lẻ gồm N - 1 số là chi phí để phá cửa.

OUTPUT:

In ra 1 số là thời gian nhỏ nhất để đến được phòng của Osama bin Laden.

​Giới hạn: 

1 <= M <= 10⁴.

1 <= N <= 10.

Chi phí của cánh cửa trong đoạn [0, 10⁴].