Bài tập

Một xã miền núi có \(N\) thôn, thôn thứ \(i\) nằm ở độ cao \(h_i\) mét so với mực nước biển. Người ta cần chọn đúng \(k\) thôn để lắp hệ thống bơm nước chung, sao cho hiệu giữa độ cao lớn nhất và độ cao nhỏ nhất trong \(k\) thôn được chọn là bé nhất có thể.

Hãy tính giá trị nhỏ nhất đó.

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(k\).
• Dòng thứ hai chứa \(N\) số nguyên \(h_1, h_2, \dots, h_N\).

Output

In ra một số nguyên là hiệu độ cao nhỏ nhất có thể đạt được.

Constraints

• \(1 \le k \le N \le 10^5\)
• \(1 \le h_i \le 10^9\)

Sample Input

7 3
10 4 20 12 5 30 11

Sample Output

2

Explanation

Chọn các thôn có độ cao \(10, 11, 12\): hiệu là \(12 - 10 = 2\), không có cách chọn nào tốt hơn.

Cho hai số nguyên dương \(a\) và \(b\) với \(a \le b\). Hãy đếm xem trong đoạn \([a, b]\) (tính cả hai đầu mút) có bao nhiêu số nguyên chẵn đồng thời chia hết cho \(3\).

Input

• Một dòng chứa hai số nguyên dương \(a, b\).

Output

• In ra số lượng các số thỏa mãn.

Constraints

• \(1 \le a \le b \le 10^{10}\)

Sample Input 1

10 100

Sample Output 1

15

Explanation

Các số cần tìm là các bội của \(6\) trong đoạn \([10, 100]\): \(12, 18, \ldots, 96\), tổng cộng \(15\) số.

Cho hai số nguyên dương \(a\) và \(b\). Hãy tìm số nguyên dương nhỏ nhất chia hết cho cả \(a\) lẫn \(b\).

Input

Một dòng gồm hai số nguyên \(a\) và \(b\).

Output

In ra bội chung nhỏ nhất của \(a\) và \(b\).

Constraints

• \(1 \le a, b \le 10^{18}\)
• Đảm bảo kết quả không vượt quá \(10^{18}\).

Sample Input 1

4 6

Sample Output 1

12

Sample Input 2

9 3

Sample Output 2

9

Bác Sắn có \(N\) chiếc bình gốm cổ được xếp thẳng hàng trong một chiếc hộp dài mở hai đầu, bình thứ \(i\) có giá trị gốc \(v_i\). Mỗi ngày bác chỉ bán được một bình và chỉ được lấy bình ở đầu trái hoặc đầu phải của hàng bình còn lại.

Bình càng để lâu càng quý: nếu bình có giá trị gốc \(v\) được bán vào ngày thứ \(a\) (ngày đầu tiên là \(a = 1\)) thì bác thu được \(v \cdot a\) đồng.

Hãy tìm cách bán hết \(N\) bình để tổng số tiền thu được là lớn nhất, và in ra số tiền đó.

Input

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(v_1, v_2, \dots, v_N\) theo thứ tự xếp trong hộp.

Output

In ra một số nguyên là tổng tiền lớn nhất có thể thu được.

Constraints

• \(1 \le N \le 2000\)
• \(1 \le v_i \le 1000\)

Sample Input

6
2 7 3 1 9 4

Sample Output

103

Explanation

Cách bán tối ưu: lấy bình ở đầu trái bốn lần, rồi lấy hai bình ở đầu phải. Thứ tự bán là \(2, 7, 3, 1, 4, 9\) vào các ngày \(1, \dots, 6\): \(2\cdot1 + 7\cdot2 + 3\cdot3 + 1\cdot4 + 4\cdot5 + 9\cdot6 = 103\).