Kyoto là một địa điểm du lịch nổi tiếng thế giới, cũng nổi tiếng với mạng đường phố dạng ô bàn cờ. Bạn đang tham quan thành phố và muốn đi bộ đến một danh lam thắng cảnh nhanh nhất có thể. Bài toán xét mô hình đơn giản sau.

Thành phố có \(H\) con đường chạy theo hướng đông-tây và \(W\) con đường chạy theo hướng nam-bắc, chia thành phố thành lưới \((H-1)\times(W-1)\) ô vuông. Giao điểm của đường thứ \(i\) tính từ phía bắc (\(1\le i\le H\)) và đường thứ \(j\) tính từ phía tây (\(1\le j\le W\)) được ký hiệu là \((i,j)\).

Độ rộng, vật liệu và mức độ đông đúc của các đường khác nhau, nên tốc độ đi bộ trên chúng có thể khác nhau:

• Đi một đơn vị độ dài trên đường thứ \(i\) từ phía bắc mất \(A_i\) giây. Cụ thể, với mỗi \(1\le c\le W-1\), đi từ giao điểm \((i,c)\) đến \((i,c+1)\) mất \(A_i\) giây.
• Đi một đơn vị độ dài trên đường thứ \(j\) từ phía tây mất \(B_j\) giây. Cụ thể, với mỗi \(1\le r\le H-1\), đi từ giao điểm \((r,j)\) đến \((r+1,j)\) mất \(B_j\) giây.

Để không làm ảnh hưởng cảnh quan đẹp của Kyoto, bạn không được đi ra ngoài các con đường.

Bạn đang ở giao điểm \((1,1)\) và muốn đến \((H,W)\). Vì đi xa sẽ mệt, bạn không muốn đi vòng: bạn không bao giờ đi về phía bắc hoặc phía tây. Với điều kiện này, hãy tính thời gian ít nhất để đến đích.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả giá trị đều là số nguyên.

H W
A_1 A_2 ... A_H
B_1 B_2 ... B_W

Dữ liệu ra

In một dòng chứa thời gian ít nhất, tính bằng giây, để đi bộ từ \((1,1)\) đến \((H,W)\) mà không đi vòng.

Ràng buộc

• \(2\le H\le 100\,000\).
• \(2\le W\le 100\,000\).
• \(1\le A_i\le 1\,000\,000\,000\) (\(1\le i\le H\)).
• \(1\le B_j\le 1\,000\,000\,000\) (\(1\le j\le W\)).

Phân nhóm

• Nhóm 1 (10 điểm): \(H\le 1\,000\), \(W\le 1\,000\).
• Nhóm 2 (30 điểm): \(A_i\le 1\,000\) với mọi \(i\), \(B_j\le 1\,000\) với mọi \(j\).
• Nhóm 3 (60 điểm): Không có ràng buộc bổ sung.

Ví dụ

2 2
1 3
2 5

5

5 5
7 1 5 2 8
7 2 4 1 6

20

4 6
454863204 543362989 866044086 813602010
71574269 17945210 688720933 392135202 38174709 168241720

2737473954

Nguồn

Bài toán thuộc JOI 2021/2022, trại huấn luyện mùa xuân, ngày thi 1 (20/03/2022). Bản gốc do JCIOI phát hành theo giấy phép CC BY-SA 4.0. Bản tiếng Việt là bản dịch từ đề chính thức.