Xưởng gạch 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 < \ldots < s_k~

Trong đó luôn có kích thước cơ bản ~s_1 = 1~.

Khách hàng cần lát kín ~m~ nền nhà. Nền nhà thứ ~j~ là hình chữ nhật có kích thước ~p_j \times q_j~. Mỗi nền chỉ được lát bằng một loại gạch vuông duy nhất có cạnh thuộc danh mục. Các viên gạch phải vừa khít theo cả hai chiều, không bị cắt và không để hở nền.

Với mỗi nền nhà, loại gạch hợp lệ có cạnh lớn nhất luôn được chọn để số viên gạch cần dùng là ít nhất.

Trong toàn bộ ~m~ nền nhà, gọi ~s_{\max}~ là kích thước cạnh lớn nhất trong số các loại gạch thực tế đã được sử dụng.

Yêu cầu

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

Input

Từ tệp văn bản TILE.INP:

• Dòng đầu tiên chứa hai số nguyên ~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, \ldots, 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 ~p_j, q_j~ ~(1 \le p_j,q_j \le 10^6)~, là kích thước nền nhà thứ ~j~.

Output

Ghi vào tệp văn bản TILE.OUT:

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

Ràng buộc

• Subtask 1 (40% số điểm): ~k,m \le 10^3~;
• Subtask 2 (40% số điểm): ~k \le 10^5~, ~m \le 10^4~;
• Subtask 3 (20% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

4 2
1 2 4 6
12 18
16 24

Output

6

Giải thích

• Nền thứ nhất chọn gạch cạnh ~6~ và dùng ~\dfrac{12}{6}\times\dfrac{18}{6}=6~ viên;
• Nền thứ hai chọn gạch cạnh ~4~ và dùng ~\dfrac{16}{4}\times\dfrac{24}{4}=24~ viên.

Kích thước lớn nhất đã được sử dụng là ~6~, nên chỉ tính ~6~ viên gạch cạnh ~6~ của nền thứ nhất.