Xếp gạch

Sau khi tham gia trò chơi "Bốc số", An tiếp tục tham gia trò chơi "Xếp gạch". Ban tổ chức cho trước $n$ chồng gạch được xếp thành một hàng ngang và đánh số từ 1 đến $n$. Số viên gạch ở các chồng lần lượt là $a_1, a_2, \dots, a_n$.

An cần thực hiện $m$ lượt chơi tương ứng với dãy số nguyên dương $b_1, b_2, \dots, b_m$ đã biết trước. Ở lượt thứ $i$ $(1 \le i \le m)$, An được quyền thực hiện chỉ một trong hai lựa chọn:

• Bỏ qua không sử dụng giá trị $b_i$.
• Xếp thêm $b_i$ viên gạch lên chồng gạch thứ $j$ $(1 \le j \le n)$ nếu tất cả các chồng gạch thứ $j, j + 1, j + 2, \dots, n$ chưa từng được xếp thêm viên gạch nào trong các lượt trước đó.

Trò chơi dừng lại khi hết lượt hoặc An đã thực hiện xếp thêm gạch ở chồng thứ $n$. Khi đó ban tổ chức sẽ đếm số gạch ở mỗi chồng và lấy số gạch ở chồng ít nhất làm điểm số của An.

Cách chơi của An là tối ưu nhất nên cậu đã đạt được số điểm tối đa của trò chơi.

Yêu cầu: Hãy tìm ra số điểm An đạt được.

Dữ liệu: Nhập từ tệp B3.INP gồm 3 dòng:

• Dòng 1: ghi hai số nguyên dương $n$ và $m$ lần lượt là số chồng gạch ban đầu và số lượt chơi của An.
• Dòng 2: ghi $n$ số nguyên không âm $a_1, a_2, \dots, a_n$ $(a_i \le 10^8)$ mô tả số gạch ở các chồng ban đầu.
• Dòng 3: ghi $m$ số nguyên dương $b_1, b_2, \dots, b_m$ $(b_i \le 10^8)$ mô tả các giá trị của ban tổ chức đưa trước cho An, $b_i$ là giá trị được sử dụng ở lượt thứ $i$.

Kết quả: Ghi ra tệp B3.OUT gồm 1 dòng chứa số điểm An đạt được.

• 40% số test tương ứng 40% số điểm thoả mãn $m = 1, 1 \le n \le 10^3$;
• 30% số test tương ứng 30% số điểm thoả mãn $m = 2$ và $10^3 < n \le 10^4$;
• 30% số test tương ứng 30% số điểm thoả mãn $10^4 < n, m \le 10^6$.