Vào một buổi sáng đẹp trời Shinoz sắp một đàn bò gồm n con bò để vắt sữa. Anh dự kiến là vào sáng hôm đó, con bò thứ i có khả năng sẽ vắt được ~a_i~ lít sữa. Tuy nhiên đàn bò của anh có đặc tính là cứ mỗi lần vắt sữa một con, những con còn lại trông thấy sợ quá nên sẽ bị giảm sản lượng mỗi con 1 lít sữa. Nếu vắt sữa con bò thứ nhất, n-1 con còn lại bị giảm sản lượng. Sau đó vắt sữa con bò thứ hai thì n-2 con còn lại bị giảm sản lượng.... Bạn hãy giúp Shinoz tính xem thứ tự vắt sữa bò như thế nào để số lượng sữa vắt được là nhiều nhất nhé.

Input:

Gồm 2 dòng:

• Dòng thứ nhất là số nguyên n (1 ≤ n ≤ 1000) là số lượng con bò.
• Dòng thứ hai gồm n số nguyên ~a_1, a_2,..., a_n (1 \le a_i \le 10000)~ là sản lượng sữa của các con bò.

Output:

• Là một số nguyên xác định số lít sữa nhiều nhất mà Shinoz có thể vắt được.

Example:

Input:

4
4 4 4 4

Output:

10

Input:

4
2 1 4 3

Output:

6

Có n người đang đứng chờ trước một thang máy duy nhất tại tầng trệt trong một tòa cao ốc cao 2000 tầng, họ muốn đi đến các tầng trong tòa nhà. Các tầng của cao ốc được đánh số 1, 2, 3, 4, ..., 2000. Tầng trệt là tầng 1. Người thứ i muốn đi đến tầng ~a_i~. Thang máy chỉ chở được k người cùng lúc. Thời gian thang máy đi từ tầng x đến tầng y là |x - y| giây.

Yêu cầu: Hãy tính thời gian tối thiểu để thang máy có thể vận chuyển hết n người đến tầng mà họ mong muốn và thang máy quay trở lại tầng trệt. Giả sử thời gian ra vào thang máy là không đáng kể.

Input:

Gồm 2 dòng:

• Dòng thứ nhất là 2 số nguyên n, k cách nhau một khoảng trắng (1 ≤ n, k ≤ 2000)
• Dòng thứ hai gồm n số nguyên ~a_i~, mỗi số cách nhau một khoảng trắng ~(2 ≤ a_i ≤ 2000)~

Output:

Là một số nguyên xác định thời gian tối thiểu để đạt được mục đích.

Example:

Input:

3 2
2 3 4

Output:

8

Input

4 2
50 100 50 100

Output

296

Input

10 3
2 2 2 2 2 2 2 2 2 2

Output

8

Một cơ sở sửa chữa ô tô có nhận n chiếc xe để sửa. Do các nhân viên làm việc quá lười nhác nên đã đến hạn trả cho khách hàng mà vẫn chưa tiến hành sửa được chiếc xe nào. Theo hợp đồng đã ký kết từ trước, nếu bàn giao xe thứ i quá hạn ngày nào thì sẽ phải trả thêm một khoản tiền phạt là A[i]. Ông chủ cơ sở sửa chữa quyết định sa thải toàn bộ công nhân và thuê nhân công mới. Với lực lượng mới này, ông ta dự định rằng để sửa chiếc xe thứ i sẽ cần B[i] ngày. Vấn đề đặt ra đối với ông là phải lập lịch sửa tuần tự các chiếc xe sao cho tổng số tiền bị phạt là ít nhất.

Yêu cầu: Hãy lập lịch sửa xe giúp cho ông chủ cơ sở sửa chữa ô tô.

Input:

• Dòng 1: Chứa số n (n ≤ 10000)
• Dòng 2: Chứa n số nguyên dương A[1], A[2], ..., A[n] (1 ≤ A[i] ≤ 10000)
• Dòng 3: Chứa n số nguyên dương B[1], B[2], ..., B[n] (1 ≤ B[i] ≤ 100)

Output:

• Dòng 1: Ghi số tiền bị phạt tối thiểu
• Dòng 2: Ghi số hiệu các xe sẽ tiến hành sửa chữa, theo thứ tự từ xe được sửa đầu tiên đến xe sửa sau cùng.

Example:

Input:

4
1 3 4 2
3 2 3 1

Output:

44
4 2 3 1 

Có N cây gỗ, có chiều cao lần lượt là ~A_1,A_2,...,A_N~. Bạn cần lấy một lượng gỗ độ cao tối thiểu là M bằng cách chặt từ N cây theo cách như sau: chặt tất cả những phần thừa của các cây có độ cao lớn hơn H.

Yêu cầu: Hãy tìm giá trị H lớn nhất để bạn có thể lấy được lượng gỗ tối thiểu là M.

Input:

• Dòng 1 chứa 2 số nguyên N và M .
• Dòng 2 chứa N số nguyên ~A_1,A_2,...,A_N~, là chiều cao mỗi cây gỗ tương ứng. Giả sử luôn tồn tại cách chặt.

Output:

• Số H duy nhất là kết quả bài toán trên.

Example:

Input:

4 7
20 15 10 17

Output:

15
Giải thích:  
Cây 1 chặt được (20-15)=5.
Cây 4 chặt được (17-15)=2.
Tổng số gỗ chặt được nếu H=15 là 7.

Constraints:

~1 \le N \le 2.10^5 ; 1 <= M <= 2.10^6 ; A_i \le 10^5~

Là một người khá bận rộn, Thầy Sơn chỉ có đúng T thời gian để làm một vài thứ thú vị và Thầy muốn làm nhiều thứ nhất có thể.

Yêu cầu: Có tất cả N công việc, em hãy giúp Thầy chọn một số công việc sao cho số lượng công việc được chọn là nhiều nhất.

Input:

• Dòng 1. Ghi 2 số nguyên dương N và T tương ứng là số lượng công việc và thời gian tối đa cho phép để làm một số công việc.
• Dòng 2. Ghi N số nguyên dương ~A_1, A_2,...,A_N~, với ~A_i~ là thời gian để hoàn thành công việc thứ i.

Output:

• In ra số nguyên dương K là số lượng công việc tối đa có thể làm trong khoảng thời gian T.

Example:

Input:

5 10
1 2 1 6 3

Output:

4

Constraints:

~0 < N,T \le 2000; 0 < A_i \le 1000~