Nhân ngày 8/3 các bạn nam đã góp quỹ được số tiền là b (~1 ≤ b ≤ 10^9~) để mua quà tặng cho ~n~ (~1 ≤ n ≤ 1000~) bạn nữ trong trường. Bạn nữ thứ ~i~ yêu cầu một món quà với giá ~p_i~. Các bạn nam có một phiếu giảm giá đặc biệt mà khi dùng phiếu giảm giá đó để mua món quà thứ ~i~ thì giá chỉ còn lại là ~s_i~ (~1 ≤ s_i ≤ p_i~).

Yêu cầu: Hãy giúp các bạn nam trong trường xác định số lượng tối đa các bạn nữ mà họ có đủ khả năng để tặng quà.

INPUT

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~b~.

• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~p_i~ và ~s_i~ (~1 ≤ s_i ≤ p_i ≤ 10^9~).

OUTPUT

• Số lượng tối đa các bạn nữ có thể được mua quà.

Ví dụ:

Input

4 8 
3 2 
2 2 
8 1 
4 3 

Output

3

Giải thích:

• Các bạn nam có thể mua quà tặng cho các bạn nữ thứ nhất, thứ hai, thứ ba, nếu họ sử dụng phiếu giảm giá cho món quà thứ ba.
  Tổng chi phí sẽ là 3 + 2 + 1 = 6.

• Lưu ý rằng các bạn nam có thể sử dụng phiếu giảm giá để mua quà cho bạn nữ thứ tư và có thể mua được các món quà cho các bạn thứ nhất, thứ hai và thứ tư.

Ràng buộc

✓ 50% số điểm/tổng điểm tương ứng với số test có n = 2.

✓ 80% số điểm/tổng điểm tương ứng với số test có n ≤ 100.

✓ 100% số điểm/tổng điểm tương ứng với số test không có ràng buộc gì.

Trong ~n~ ngày liên tiếp, Hiếu ghi lại giá vàng 9999 của từng ngày để tự đánh giá các quyết định đầu tư của mình.

Sau khi đã có toàn bộ bảng giá của ~n~ ngày đó, Hiếu muốn biết: nếu trong giai đoạn này anh ấy được thực hiện đúng một giao dịch thì lợi nhuận lớn nhất có thể đạt được là bao nhiêu.

Một giao dịch gồm:

• Chọn một ngày để mua vàng
• Chọn một ngày sau đó để bán vàng

Lợi nhuận thu được bằng: Giá bán - Giá mua

Hãy tính lợi nhuận lớn nhất mà Hiếu có thể đạt được. Nếu không có cách nào để có lãi, hãy in ra 0.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 ≤ n ≤ 2 × 10^5~)
• Dòng thứ hai chứa n số nguyên ~a_1, a_2, ..., a_n~ (~1 ≤ a_i ≤ 10^9~), trong đó ai là giá vàng ở ngày thứ ~i~.

Output

• In ra một số nguyên duy nhất là lợi nhuận lớn nhất có thể đạt được. Nếu mọi giao dịch đều không có lãi thì in ra 0.

Ví dụ

Input:

6
7 1 5 3 6 4

Output:

5

Bo đang chơi một game. Ban đầu, Bo có một vòng tròn bán kính ~k~. Trên màn hình game còn có ~n~ vòng tròn khác, vòng tròn thứ ~i~ có bán kính là ~A_i~. Bo có thề điều khiền vòng tròn của mình để chạm vào các vòng tròn khác. Mỗi khi vòng tròn của Bo chạm vào một vòng tròn khác thì một trong hai khả năng có thể xảy ra:

Nếu bán kính vòng tròn do Bo điều khiển lớn hơn hay bằng bán kính vòng tròn bị chạm vào thì vòng tròn bị chạm sẽ tan vỡ, còn vòng tròn của Bo trở nên lớn hơn và bán kính của nó sẽ bằng tổng bán kính vòng tròn hiện tại của Bo với bán kính vòng tròn bị chạm đó. Nếu bán kính vòng tròn do Bo điều khiến nhỏ hơn bán kính vòng tròn bị chạm vào thì kết thúc game. Bo chơi game rất giỏi. Bạn ấy luôn tìm cách chơi sao cho khi kết thúc game thì bán kính vòng tròn của bạn ấy là lớn nhất.

Yêu cầu: Tìm bán kính lớn nhất có thể đạt được của vòng tròn.

Input

• Dòng thứ nhất: gồm hai số nguyên dương lần lượt là ~n~ và ~k~. Trong đó, ~n~ là số lượng vòng tròn, ~k~ là bán kính vòng tròn của Bo, giữa ~n~ và ~k~ được cách nhau bởi một dấu cách. (~1 ≤ n ≤ 10^3~, ~1 ≤ k ≤ 10^6~)

• Dòng thứ hai: gồm ~n~ số nguyên dương ~A_i~ lần lượt là bán kính của ~n~ vòng tròn. (~1 ≤ A_i ≤ 10^6~)

Output

• Gồm một số nguyên dương là bán kính lớn nhất cần tìm.

Example

Input

5 4
7 68 3 2 20

Output

16

Note

• Ban dầu, có 5 vòng tròn (~n = 5~) với bán kính lần lượt là 7, 68, 3, 2, 20 và vòng tròn của Bo có bán kính là ~k~ = 4.

• Lần 1: Vòng tròn của Bo chạm vòng tròn có bán kính là 2 → vòng tròn của Bo có bán kính mới là 4 + 2 = 6.

• Lần 2: Vòng tròn của Bo chạm vòng tròn có bán kính là 3 → vòng tròn của Bo có bán kính mới là 6 + 3 = 9.

• Lần 3: Vòng tròn của Bo chạm vòng tròn có bán kính là 7 → vòng tròn của Bo có bán kính mới là 9 + 7 = 16.

Đến đây, còn hai vòng tròn có bán kính là 20 và 68. Hai bán kính này đều lớn hơn bán kính vòng của Bo nên kết thúc game.

Vậy bán kính lớn nhất cần tìm là 16.

Trong một đợt thanh lý hàng cũ, cửa hàng ~X~ cần bán ~n~ máy tính có cấu hình giống nhau. Có ~m~ khách hàng đồng ý mua các máy tính này, mỗi khách hàng sẽ mua 1 cái. Khách hàng thứ ~i~ (~i=1..m~) sẽ đồng ý mua nếu như giá bán của mỗi chiếc máy tính không vượt quá ~a_i~. Cửa hàng cần định ra một mức giá bán sao cho tổng số tiền thu về là lớn nhất.

Ví dụ: nếu có 5 cái máy tính và có 4 khách hàng đặt mua với mức giá là: 2,8,10,7. Nếu cửa hàng định mức giá là 2 thì cả 4 người đều mua được nhưng số tiền mà cửa hàng thu được chỉ là ~2x4=8~; Nếu cửa hàng định mức giá là 10 thì chỉ bán được cho 1 khách hàng nhưng số tiền thu được là 10; Phương án tối ưu là định giá là 7, khi đó bán được cho 3 khách hàng với số tiền thu về lớn nhất bằng 21.

Dữ liệu vào:

• Dòng đầu tiên ghi hai số nguyên dương ~n,m~ (~n,m \le 10^5~).
• Dòng thứ hai ghi các số ~a_1,a_2,...,a_n~. Mỗi số có giá trị không vượt quá 1000.

Kết quả:

• Dòng 1: Ghi ra một số nguyên duy nhất là số tiền lớn nhất thu được.

Ví dụ:

Input

5 4
2 8 10 7

Output

21

Cho ~n~ tiểu hành tinh có khối lượng lần lượt là ~a_1,a_2,...,a_n~ và một số nguyên k biểu thị khối lượng của hành tinh. Khi hành tinh va chạm với tiểu hành tinh, nếu khối lượng của hành tinh lớn hơn hoặc bằng khối lượng của tiểu hành tinh, tiểu hành tinh đó sẽ bị phá hủy và hành tinh sẽ nhận được khối lượng của tiểu hành tinh. Nếu không, hành tinh bị phá hủy.

Yêu cầu: Nhiệm vụ của bạn là hãy chọn trật tự va chạm với các tiểu hành tinh như thế nào để hành tinh không bị phá vỡ.

Dữ liệu vào:

• Dòng 1. Ghi 2 số nguyên dương ~n~,~k~.

• Dòng 2: Ghi ~n~ số nguyên dương lần lượt là khối lượng của các tiểu hành tinh.

  Dữ liệu ra:

• Nếu có thể phá hủy được tất cả cá tiểu hành thì in ra khối lượng của hành tinh sau khi va chạm với tất cả các tiểu hành tinh, ngược lại ghi 'Skills issue'.

Ví dụ 1

Input1

5 10
3 9 19 5 21

Output1

67

Input2

4 5
4 9 23 4

Output2

Skills issue

Ràng buộc

• ~1 ≤ n ≤ 10^5~; ~0 ≤ a_i ≤ 10^9~;
• ~1 ≤ k ≤ 10^{14}~

Sau trận đại dịch Covid-19 năm 2020, nhiều tỉnh thành đã rơi vào hoàn cảnh khốn khó. Với tinh thần đoàn kết tương trợ, doanh nghiệp ~A~ dự định lên kế hoạch sẽ tổ chức đi thiện nguyện đến vùng cao. Địa điểm đầu tiên doanh nghiệp ~A~ dự tính đến là các đồng bào có hoàn cảnh khó khăn thuộc tỉnh Lai Châu.

Trong chuyến đi này, có ~n~ đoàn tham gia, được đánh số từ ~1~ đến ~n~ (~0 < n ≤ 10^6~). Mỗi đoàn sẽ đến thăm và tặng quà cho bà con tại một ngôi làng trong huyện trên địa bàn tỉnh Lai Châu. Trong đó, đoàn thứ ~i~ sẽ di chuyển đến ngôi làng cách thành phố Lai Châu với quãng đường ~d_i~ km (~1 ≤ d_i ≤ 10^6~).

Doanh nghiệp ~A~ mong muốn chuyến đi diễn ra kịp thời, đúng tiến độ nên phải chuẩn bị ~m~ chiếc xe được đánh số từ ~1~ đến ~m~ (~n ≤ m ≤ 10^6~). Các xe được đổ đầy nhiên liệu, xe thứ ~j~ có mức tiêu thụ nhiên liệu ~v_j~ (~1 ≤ v_j ≤ 10^6~) đơn vị thể tích/km.

Yêu cầu: Để quá trình vận chuyển thuận lợi và ít tốn kém cho doanh nghiệp, bộ phận kế toán phải tính thế nào để chọn được ~n~ chiếc xe phục vụ chuyến đi sao cho tổng chi phí nhiên liệu được sử dụng là ít nhất (biết rằng mỗi xe chỉ phục vụ một đoàn).

Input

• Dòng đầu tiên ghi hai số nguyên dương ~n, m~ (các số cách nhau một khoảng trắng).

• Dòng thứ hai ghi các số nguyên dương ~d_1, d_2, …, d_n~ (các số cách nhau một khoảng trắng).

• Dòng thứ ba ghi các số nguyên dương ~v_1, v_2, …, v_m~ (các số cách nhau một khoảng trắng).

Output

• Dòng đầu tiên ghi tổng số nhiên liệu cần dùng cho việc đưa các đoàn đi thiện nguyện (chỉ tính lượt đi).

• Dòng thứ hai ghi chỉ số xe phục vụ chuyến đi theo thứ tự tăng dần của nhiên liệu bị tiêu tốn (các số cách nhau một khoảng trắng).

Scoring

• Có 25% test tương ứng 25% số điểm của bài với ~1 ≤ n, m ≤ 50, d_i, v_j ≤ 10^2~.

• Có 25% test tương ứng 25% số điểm của bài với ~1 ≤ n, m ≤ 100, d_i, v_j ≤ 10^3~.

• Có 25% test tương ứng 25% số điểm của bài với ~1 ≤ n, m ≤ 10^3, d_i, v_j ≤ 10^6~.

• Có 25% test tương ứng 25% số điểm của bài với ~1 ≤ n, m ≤ 10^6, d_i, v_j ≤ 10^6~.

Example

Input

3 4
2 5 9
22 13 23 10

Output

199
4 2 1 

Cho dãy số nguyên gồm các số từ ~1 -> n~ . Tìm cách chèn ~(n-1)~ dấu ~'+'~ hoặc ~'–'~ vào giữa các số sao cho khi tính biểu thức đó cho kết quả là ~S~.

Yêu cầu: chèn ít dấu trừ nhất có thể

Input :

• Cho ~n~ và ~S~ (~1 ≤ n ≤ 500, |S| ≤ 125250~)

Output :

• Nếu có xuất ra biểu thức, không thì xuất 'Impossible'

Ví dụ:

Input:

9 5

Output:

1+2-3+4+5+6+7-8-9

Input:

5 6

Output:

Impossible

Trong nhà Nam đang có ~n~ ổ cắm điện rời. Số lượng chổ cắm trên mỗi ổ cắm điện này lần lượt là ~a_1,a_2,..a_n~ chổ cắm điện. Trên tường nhà Nam có một chổ cắm cố định đang có điện. Vậy để cho một ổ cắm điện rời có điện thì phải cắm ổ cắm đó vào chỗ cắm cố định trên tường. Chúng ta cũng có thể cắm ổ cắm điện rời này vào một ổ cắm điện rời khác đang có điện. Nam có ~m~ thiết bị sử dụng điện, để sử dụng thì các thiết bị này cần được cắm vào ổ cắm trên tường hoặc ổ cắm rời đang có điện. Bạn hãy giúp Nam tìm ra số ổ cắm rời ít nhất cần dùng để có thể sử dụng tất cả m thiết bị điện này.

Dữ liệu vào:

Được cho bởi tệp CAMDIEN.INP có cấu trúc như sau:

• Dòng thứ nhất gồm 1 số nguyên ~n~,~m~. Dữ liệu vào đảm bảo ~1 ≤ n,m ≤ 10^5~, n là số lượng ổ cắm và m là số lượng thiết bị.
• Dòng thứ 2 gồm n số nguyên ~a_1,a_2,..,a_n~ là số chổ cắm trên các ổ cắm rời tương ứng, với mỗi số cách nhau 1 dấu cách (~1 ≤ a_i ≤ 10^5~)

Dữ liệu ra:

Được cho bởi tệp CAMDIEN.OUT có cấu trúc như sau:

• Ghi ra số nguyên cho biết số ổ cắm rời ít nhất cần sử dụng là bao nhiêu. Nếu đã sử dụng hết tất cả ổ cắm rời mà vẫn không đủ thì in ra -1.

Ví dụ:

Input1

3 4
3 2 2   

Output1

2

Input2

5 5
1 3 1 2 1   

Output2

-1

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

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~

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 

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ông ty đồ chơi ~X~ nhập khẩu ~N~ con búp bê gỗ. Các con búp bê được đánh số từ 1 tới ~N~ trong đó con búp bê thứ ~i~ là một hộp rỗng có kích thước là một số nguyên ~A_i~. Người ta có thể lồng con búp bê thứ i vào trong con búp bê thứ ~j~ nếu con búp bê thứ ~j~ đang rỗng và ~A_i+k≤ A_j~, với ~K~ là một số nguyên dương cho trước. Bằng cách lồng các con búp bê vào nhau theo cách như vậy, công ty ~X~ chỉ cần tìm chỗ đặt những con búp bê ngoài cùng (những con búp bê không nằm trong bất kỳ con búp bê nào khác) vào kho.

Yêu cầu: Hãy giúp công ty ~X~ lồng các con búp bê vào nhau sao cho tổng kích thước các con búp bê ngoài cùng là nhỏ nhất.

Input:

Gồm 2 dòng:

• Dòng 1 chứa hai số nguyên dương cách nhau một khoảng trắng.

• Dòng 2 chứa n số nguyên dương ~A_1~, ~A_2~,...,~A_N~ , mỗi số cách nhau một khoảng trắng.

Output:

• Là một số nguyên duy nhất là tổng kích thước các con búp bê ngoài cùng theo phương án tìm được.

Example:

Input:

8 2
8 4 2 1 1 3 5 9

Output:

18

Constraint:

~N \le 10^5~; ~K \le 10^9~; ~A_i ≤ 10^9~