Xưởng gạch của kiến trúc sư Phú Vinh chỉ sản xuất gạch lát nền hình vuông với cạnh thuộc một danh mục cố định gồm ~k~ kích thước: ~s_1 < s_2 < \dots < s_k~ (đơn vị: cm), trong đó luôn có kích thước cơ bản ~s_1 = 1~.

Khách hàng đặt lát kín ~m~ nền nhà (được đánh số từ ~1~ đến ~m~). Nền nhà thứ ~j~ là một hình chữ nhật có kích thước ~p_j \times q_j~ (cm). Mỗi nền nhà chỉ được lát kín bằng một loại gạch vuông duy nhất có kích thước cạnh ~s \in \lbrace s_1, s_2, \dots, s_k \rbrace~ sao cho ta có thể xếp các viên gạch ấy nguyên vẹn vừa khít dọc theo cả chiều dài ~p_j~ và chiều rộng ~q_j~ (đảm bảo không phải cắt gạch và không để hở nền).

Để tiết kiệm thời gian và công sức, với mỗi nền nhà, Phú Vinh luôn chọn loại gạch hợp lệ có kích thước cạnh lớn nhất để số lượng viên gạch cần dùng là ít nhất.

Trong quá trình thi công toàn bộ ~m~ nền nhà, sẽ có một loại gạch mang kích thước lớn nhất được đem ra sử dụng (gọi là kích thước ~s_{max}~).

Yêu cầu: Hãy tính tổng số lượng viên gạch mang kích thước ~s_{max}~ đã được dùng để lát các nền nhà.

Dữ liệu vào

• Dòng đầu tiên là hai số nguyên dương ~k, m~ ~(2 \le k, m \le 10^6)~.
• Dòng thứ hai chứa ~k~ số nguyên dương tăng dần ~s_1 < s_2 < \dots < s_k~ ~(1 \le s_i \le 10^6)~, với ~s_1 = 1~.
• ~m~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên dương ~p_j~ và ~q_j~ ~(1 \le p_j, q_j \le 10^6)~ thể hiện kích thước của nền nhà thứ ~j~.

Kết quả

• Một số nguyên duy nhất là tổng số lượng viên gạch mang kích thước lớn nhất đã được sử dụng.

Ví dụ

Input

4 2
1 2 4 6
12 18
16 24

Output

6

Giải thích:

• Nền 1 (~12 \times 18~): Các cạnh gạch hợp lệ có trong danh mục là ~1, 2, 6~. Để tốn ít gạch nhất, ta chọn loại gạch có cạnh ~6~. Lát kín nền này cần sử dụng hết ~6~ viên gạch.
• Nền 2 (~16 \times 24~): Các cạnh gạch hợp lệ có trong danh mục là ~1, 2, 4~. Ta chọn loại gạch có cạnh ~4~. Lát kín nền này cần sử dụng hết ~24~ viên gạch.
• So sánh hai loại gạch đã dùng (cạnh ~6~ và cạnh ~4~), loại gạch có kích thước lớn nhất là ~6~. Số lượng viên gạch cạnh ~6~ đã dùng trên toàn bộ công trình là ~6~ viên.

Giới hạn

• ~2 \le k, m \le 10^6~.
• ~1 \le s_i \le 10^6~, dãy ~s~ tăng dần và ~s_1 = 1~.
• ~1 \le p_j, q_j \le 10^6~.

Subtask:

• 40% số test tương ứng với 40% số điểm có ~k, m \le 10^3~.
• 40% số test tương ứng với 40% số điểm có ~k \le 10^5, m \le 10^4~.
• 20% số test tương ứng với 20% số điểm còn lại không có giới hạn gì thêm.