An có đủ bộ truyện Doraemon mới tái bản gồm \(n\) tập đánh số từ \(1\) tới \(n\), tập thứ \(i\) có độ dài là \(t_i\) trang. Vì các bạn trong lớp đều muốn đọc nên An muốn tạo ra một kế hoạch đọc truyện cho các bạn sao cho hợp lý nhất. Có \(m\) bạn muốn đọc truyện, họ phải bốc thăm và đánh số từ \(1\) tới \(m\) theo thứ tự từ người sẽ được đọc đầu tiên tới người sẽ được đọc sau cùng. Nếu một bạn có tốc độ đọc \(C\) giây/trang thì để đọc tập thứ \(i\), bạn đó sẽ mất thời gian là \(C \cdot t_i\).

Tất cả các bạn đều muốn đọc bộ truyện theo đúng thứ tự từ tập \(1\) tới tập \(n\), hơn thế nữa khi đọc xong một tập, họ muốn có thể đọc ngay tập tiếp theo mà không mất thời gian chờ đợi:

• Đầu tiên An cho bạn thứ nhất mượn từng tập, đọc xong tập nào trả lại ngay cho An tập đó và mượn tập kế tiếp...
• Tới bạn thứ hai, An cũng cho mượn theo cách như vậy. Nhưng nhờ biết tốc độ đọc của bạn thứ nhất, An phải tính toán thời điểm bắt đầu cho bạn thứ hai đọc tập \(1\) để khi bạn thứ hai đọc xong mỗi tập \(i\) thì tập \(i + 1\) đã được bạn thứ nhất trả lại cho An cho bạn thứ hai mượn.
• Tương tự như vậy với các bạn thứ \(3, 4, \dots, m\). An phải tính toán thời điểm mỗi người bắt đầu đọc tập \(1\) để không có bạn nào phải chờ đợi tập kế tiếp mỗi khi đọc xong một tập...

Yêu cầu: Biết tốc độ đọc của \(m\) bạn là \(c_1, c_2, \dots, c_m\). Tính thời điểm sớm nhất mà bạn cuối cùng đọc xong bộ truyện. Biết rằng người \(1\) bắt đầu đọc từ thời điểm \(0\).

Ví dụ với \(n = 3\) tập, \(m = 3\) bạn, \(t = (1, 2, 1)\), \(c = (10, 10, 2)\). Cách đọc kết thúc sớm nhất và các khoảng thời gian đọc truyện trong lịch có thể cho trong bảng sau:

Input

• Dòng 1 chứa hai số nguyên dương \(n, m \le 10^5\).
• Dòng 2 chứa \(n\) số nguyên dương \(t_1, t_2, \dots, t_n \le 10^5\).
• Dòng 3 chứa \(m\) số nguyên dương \(c_1, c_2, \dots, c_m \le 10^5\).
• Các số trên một dòng của input được ghi cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên duy nhất là thời điểm người cuối cùng đọc xong bộ truyện.

Example

3 3
1 2 1
10 10 2

62