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

Trên một trục đường dài thẳng có \(n\) trạm xe buýt cách đều nhau, các trạm được đánh số từ \(1\) đến \(n\). Để đi lại giữa hai trạm liên tiếp bất kì bằng xe buýt mất \(a\) đồng. Trong \(n\) trạm có \(m\) trạm đặc biệt là các trạm \(p_1, p_2, ..., p_m (1 \leq p_1, p_2, \dots , p_m \leq n)\). Có loại xe buýt nhanh sẽ chỉ dừng đỗ tại các trạm đặc biệt này, nếu sử dụng xe buýt nhanh để đi từ trạm đặc biệt \(p_i\) đến trạm đặc biệt \(p_j\) sẽ mất \(b\) x \(|p_i - p_j|\) đồng.

Yêu cầu: Cho \(q\) câu hỏi, câu hỏi thứ \(k\) \((1 \leq k \leq q)\) cần trả lời đi từ trạm \(x_k\) \((1 \leq x_k \leq n)\) tới trạm \(y_k\) \((1 \leq y_k \leq n)\) hết ít nhất bao nhiêu tiền.

Input

• Dòng đầu chứa các số nguyên dương \(n, m, q, a, b\) \((a, b \leq 10^6; 2 \leq m \leq n);\)
• Dòng thứ hai chứa \(m\) số nguyên dương \(p_1, p_2, \dots, p_m;\)
• Dòng thứ \(k\) \((1 \leq k \leq q)\) chứa hai số nguyên dương \(x_k, y_k\).

Output

• Ghi ra thiết bị ra chuẩn gồm \(q\) dòng, dòng thứ \(k\) chứa một số là câu trả lời cho câu hỏi thứ \(k\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n, m, q \leq 100; a = b\)
• Subtask \(2\) (\(25\%\) số điểm): \(n, m \leq 100; m = 2; p_1 = 1; p_2 = n\)
• Subtask \(3\) (\(25\%\) số điểm): \(n, m, q \leq 100\)
• Subtask \(4\) (\(25\%\) số điểm): \(n, m, q \leq 10^6\).

Example

5 2 2 2 1
2 4
1 5
2 3 

6
2

Cho dãy số nguyên \(A = (a_1, a_2, ..., a_n)\). Với hai số nguyên dương \(l, r(1 \leq l \leq r \leq n)\), gọi trọng số của cặp \((l, r)\) là tổng giá trị của các phần tử liên tiếp từ \(l\) đến \(r\) của dãy \(A\).

Yêu cầu: Cho dãy A và số nguyên k, hãy chọn ra k cặp \((l_1, r_1), (l_2, r_2), ..., (l_k, r_k)\) thõa mãn:

• \(1 \leq l_i \leq r_i \leq n\)
• Các cặp này đôi một khác nhau
• \(X \leq r_i - l_i + 1\)
• Tổng trọng số của \(k\) cặp đã chọn là lớn nhất

Input

• Dòng đầu chứa ba số nguyên dương \(n, k, X\)
• Dòng thứ hai chứa n số nguyên \(a_i (|a_i| \leq 10^5)\)

Output

• Ghi ra một số nguyên duy nhất là tổng trọng số lớn nhất tìm được.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \leq 100; k \leq 1000\)
• Subtask \(2\) (\(15\%\) số điểm): \(n \leq 1000; k \leq 10^5\)
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^4; k \leq 10^4\)
• Subtask \(4\) (\(20\%\) số điểm): \(n, k \leq 5 \cdot 10^4\)
• Subtask \(5\) (\(20\%\) số điểm): \(n, k \leq 3 \cdot 10^5\)
• Subtask \(6\) (\(15\%\) số điểm): \(n \leq 3 \cdot 10^5; k \leq 10^7\).

Example

4 4 2
3 2 -6 8 

18

Một lớp học có \(n\) học sinh, các học sinh được đánh số từ 1 đến \(n\). Thầy giáo chủ nhiệm muốn chọn ra một nhóm bạn để tham gia một trò chơi, một trò chơi cần sự phối hợp nhịp nhàng giữa các thành viên trong nhóm. Là một giáo viên nhiều kinh nghiệm, thầy giáo chủ nhiệm đã biết được sự phối hợp của \(m\) cặp học sinh, một cặp học sinh \(i(1 \leq i \leq n)\) và học sinh \(j(1 \leq j \leq n)\) có sự phối hợp là giá trị \(c(i, j)\), điều này có nghĩa là nếu học sinh \(i\) và học sinh \(j\) cùng được chọn vào nhóm thì tổng sự phối hợp của nhóm sẽ được cộng giá trị \(c(i, j)\), biết rằng \(-10^9 \leq c(i, j) \leq 10^9\).

Yêu cầu: Cho \(n\) học sinh và \(m\) cặp học sinh mà thầy giáo chủ nhiệm đã biết, hãy giúp thầy giáo chủ nhiệm chọn ra một nhóm để tổng sự phối hợp của nhóm là lớn nhất.

Input

• Dòng đầu tiên chứa các số nguyên \(n, m\).
• Dòng thứ \(k(1 \leq k \leq m)\) trong \(m\) dòng tiếp theo chứa 3 số nguyên \(i_k, j_k, c(i_k, j_k)\).

Output

• Dòng đầu tiên chứa số nguyên \(s\) là số học sinh trong nhóm.
• Dòng thứ hai gồm số \(s\) là chỉ số các bạn học sinh được chọn.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 20\)
• Subtask \(2\) (\(40\%\) số điểm): \(n \leq 200\) và giá trị \(c(i, j)\) chỉ nhận một trong hai loại giá trị \(1\) hoặc \(-10^9\)
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 200\)

** Cách tính điểm **

Có \(20\) test, mỗi test \(5.0\) điểm. Với mỗi test, gọi tổng sự phối hợp của nhóm do thí sinh tìm được là \(c, q\), là tổng sự phối hợp của nhóm trong lời giải của Ban giám khảo, nếu \(c \leq 0\) thí sinh sẽ được \(0\) điểm, ngược lại số điểm của thí sinh đạt được là \(5.0 \cdot min\left(1, \dfrac{c^3}{q^3}\right)\)

Example

5 4
1 5 1
1 2 -1
2 5 3
1 4 -1 

3
1 2 5