Cho các số nguyên không âm \(a_1, b_1, a_2, b_2, a_3, b_3\). Hãy đếm số bộ ba \((x, y, z)\) thỏa mãn:

• \(a_1 \leq x \leq b_1\)
• \(a_2 \leq y \leq b_2\)
• \(a_3 \leq z \leq b_3\)
• \(x \times y = z\).

Input

• Dòng đầu tiên chứa 6 số nguyên không âm \(a_1, b_1, a_2, b_2, a_3, b_3\), các số có giá trị không vượt quá \(10^9\).

Output

• Ghi ra một số duy nhất là số bộ thỏa mãn đếm được.

Scoring

• Subtask \(1\) (\(18\%\) số điểm): \(b_1, b_2, b_3 \leq 300\);
• Subtask \(2\) (\(12\%\) số điểm): \(b_1, b_2, b_3 \leq 3000\);
• Subtask \(3\) (\(20\%\) số điểm): \(b_1, b_2, b_3 \leq 10^5\);
• Subtask \(4\) (\(20\%\) số điểm): \(b_1, b_2, b_3 \leq 10^7\);
• Subtask \(5\) (\(16\%\) số điểm): \(a_1 = b_1\);
• Subtask \(6\) (\(24\%\) số điểm): không có ràng buộc gì thêm.

Example

6 8 4 5 27 35 

4

Trong buổi giao lưu giữa các thí sinh của kì thi Tin học trẻ, có học sinh xếp thành một hàng, học sinh đứng thứ \(i(1 \leq i \leq n)\) đến từ tỉnh có mã là số nguyên \(c_i(1 \leq c_i \leq 63)\). Ban tổ chức muốn tách hàng để nhận được \(g\) nhóm học sinh tham gia một trò chơi. Cụ thể, Ban tổ chức cần chọn ra \(g - 1\) điểm cắt \(1 < k_1 < k_2 ... < k_{g-1} < n\), khi đó các bạn từ đầu hàng đến bạn đứng thứ \(k_1\) sẽ xếp vào nhóm thứ nhất, các bạn đứng thứ \(k_1 + 1\) đến \(k_2\) sẽ xếp vào nhóm thứ hai,..., bạn đứng thứ \(k_{g-1} + 1\) đến \(n\) xếp vào nhóm thứ \(g\). Độ phong phú của một nhóm được tính bằng số lượng tỉnh khác nhau của học sinh trong nhóm. Để các thí sinh có nhiều cơ hội giao lưu với nhau, Ban tổ chức muốn tìm cách tách hàng \(g\) thành nhóm để tổng độ phong phú của \(g\) nhóm là lớn nhất.

Yêu cầu: Cho dãy số nguyên dương \(c_1, c_2, ..., c_n\) và số nguyên dương \(g\), hãy tìm cách tách hàng thành \(g\) nhóm để tổng độ phong phú của nhóm là lớn nhất.

Input

• Dòng đầu tiên chứa các số nguyên \(n, g\);
• Dòng thứ hai chứa n số nguyên dương \(c_1, c_2, ..., c_n\).

Output

• Ghi ra một dòng chứa một số là tổng độ phong phú của \(g\) nhóm là lớn nhất tìm được.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 1000; g = 2\)
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 1000; g = 3\)
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 1000; g \leq 30\)
• Subtask \(4\) (\(25\%\) số điểm): \(n \leq 10^5; g \leq 30\)

Example

5 2
1 2 1 3 3 

4