Sắp xếp

Cho một dãy gồm \(N\) số nguyên dương \(A_1, A_2,…, A_N\).(\(N ≤ 10^4, A_i ≤ 10^9\)) và số \(K\) (\(K ≤ N\)). Hãy in ra số nhỏ thứ \(K\) trong dãy.

Input

• Dòng đầu chứa số \(N, K\),
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2,…, A_N\).

Output

• Một dòng chứa dãy số nhỏ thứ \(K\) trong dãy.

Example

6 4    
91 451 43 3 452 54 

91

Cho một dãy gồm \(n\) số nguyên dương \(A_1, A_2,…, A_n\). (\(N ≤ 10^4, A_i ≤ 10^9\)). Hãy in ra dãy số sau khi sắp xếp dãy số giảm dần (\(A_i ≥ A_{i+1}\)).

Input

• Dòng đầu chứa số \(n\),
• Dòng thứ hai chứa \(n\) số nguyên dương \(A_1, A_2,…, A_n\).

Output

• Một dòng chứa dãy số đã sắp xếp giảm dần.

Example

6
91 451 43 3 451 54 

451 451 91 54 43 3

Cho một dãy gồm \(N\) số nguyên dương \(A_1, A_2,…, A_N\).(\(N ≤ 10^4, A_i ≤ 10^9\)) và số \(K\) (\(K ≤ N\)). Hãy in ra số lớn thứ \(K\) trong dãy.

Input

• Dòng đầu chứa số \(N, K\),
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2,…, A_N\).

Output

• Một dòng chứa dãy số lớn thứ \(K\) trong dãy.

Example

6 2    
91 451 43 3 452 54 

451

Yugi có \(N\) lá bài, lá bài thứ \(i\) có sức mạnh như sau:

Nếu \(A_i \ge 0\) máu của Yugi sẽ được cộng thêm \(A_i\).

Nếu \(A_i <0\) máu của Kaiba sẽ trừ đi \(|A_i|\).

Tuy nhiên, Yugi luôn thích tấn công nên anh ta muốn trừ máu Kaiba nhiều nhất có thể.

Hãy cho biết Yugi có thể trừ Kaiba nhiều nhất là bao nhiêu khi sử dụng nhiều nhất \(m\) lá bài

Input

• Dòng đầu chứa số \(n, m (1 \leq m \leq n \leq 10000)\)
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2,…, A_n (-10000 \leq A_i \leq 10000)\).

Output

• Số máu Kaiba bị trừ.

Example

 5 3 
-6 0 35 -2 4  

8

Vào một buổi sáng, rất tình cờ Nam nhìn thấy một số nguyên dương \(N\) trên đường từ nhà đến trường. Vì Nam rất thích số \(30\) nên Nam muốn biến đổi số \(N\) thành số \(M\) có dạng là số lớn nhất và là bội của số \(30\) bằng cách thay đổi vị trí của các chữ số trong số \(N\) mà Nam nhìn thấy.

Bạn hãy hỗ trợ Nam bằng cách viết chương trình để tìm số \(M\) (nếu nó tồn tại).

Input

• Gồm một dòng duy nhất chứa số nguyên \(N\) (\(N\) có tối đa là \(10^5\) chữ số).

Output

• In ra số \(M\) tìm được. Nếu không tồn tại \(M\) thì in ra \(-1\).

Example

30 

30

102

210

3333333333333333333333333333 

-1

Trong Liên minh huyền thoại có \(N\) vị tướng, vị tướng thứ \(i\) có \(2\) sát thương vật lý và sát thương phép.

Vị tướng thứ \(i\) được cho là mạnh hơn vị tướng thứ \(j\) nếu có sát thương vật lý mạnh hơn.

Hai vị tướng có cùng sát thương vật lý thì vị tướng mạnh hơn sẽ có sát thương phép lớn hơn.

Hãy cho biết chỉ số sát thương vật lý và phép của vị tướng mạnh thứ \(m\).

Input

• Dòng đầu chứa số \(n, m (1 \leq m \leq n \leq 10000)\)
• \(n\) dòng, mỗi dòng chứa 2 số nguyên \(A_i(\)vật lý\(),B_i(\)phép\() (0 \leq A_i,B_i \leq 10000)\).

Output

• Chỉ số sát thương

Example

3  2
1  2
3  2
1  3   

1  3

Rùa là một cậu bé rất bận rộn. Để làm việc hiệu quả, cậu hay xem xét những công việc quan trọng trong ngày và lập một bản kế hoạch. Trong một ngày, mỗi công việc của cậu sẽ xảy ra vào một thời điểm \(hh:mm\), và cậu sẽ sắp xếp các công việc theo thứ tự tăng dần của thời điểm mà chúng diễn ra. Biết rằng, không có hai công việc nào cùng xảy ra trong cùng một thời điểm.

Sau khi lập kế hoạch thủ công nhiều lần, Rùa đã phát ngán việc này rồi, cậu nhờ bạn viết giúp cậu một chương trình có thể làm được điều này.

Input

• Dòng đầu tiên chứa một số nguyên dương \(N\) \((1 \leq N \leq 1440)\)

• \(N\) dòng tiếp theo, mỗi dòng chứa hai xâu ký tự được cách nhau bởi 1 ký tự khoảng trống.

  1. Xâu ký tự đầu tiên được cho ở định dạng là \(hh:mm\), với \((0 \leq hh \leq 23)\) và \((0 \leq mm \leq 59)\). Xâu này luôn được cho có 5 ký tự. Nếu thời điểm là 6 giờ 9 phút, thì xâu được cho sẽ là 06:09.
  2. Xâu ký tự thứ hai là tên của công việc đó. Xâu này có độ dài ít nhất 1 ký tự và nhiều nhất 50 ký tự. Chỉ chứa ký tự La-tinh in thường và ký tự -.

• Dữ liệu cho đảm bảo không có hai công việc nào cùng tên hoặc cùng thời điểm diễn ra.

Output

• In ra \(N\) công việc đã được sắp xếp. Với mỗi công việc in ra trên một dòng hai xâu ký tự là thời điểm diễn ra và tên công việc, cách nhau bởi một ký tự khoảng trống. Lưu ý, xâu thời điểm phải có 5 ký tự.

Example

5
07:00 an-sang-voi-obama
13:00 di-tap-gym 
09:21 check-mail
09:14 mua-tra-sua
15:00 meeting-voi-donald-trump

07:00 an-sang-voi-obama
09:14 mua-tra-sua
09:21 check-mail
13:00 di-tap-gym
15:00 meeting-voi-donald-trump

4
22:00 doc-truyen-ma
22:01 khong-doc-truyen-ma-nua
22:02 di-ngu
06:00 di-hoc

06:00 di-hoc
22:00 doc-truyen-ma
22:01 khong-doc-truyen-ma-nua
22:02 di-ngu

Một lời quảng cáo chào hàng trong một hiệu sách “mua 3, tặng 1, trả tiền 2”. Vì vậy, mỗi khách mua ba quyển sẽ được tặng một quyển có giá rẻ nhất trong ba quyển. Và tất nhiên, khách hàng có thể mua nhiều sách, phụ thuộc vào việc sắp xếp các quyển sách vào mỗi nhóm ba quyển để được miễn phí quyển có giá rẻ nhất trong nhóm đó.
Ví dụ, khách hàng lấy các quyển sách có giá 10, 3, 2, 4, 6, 4, 9. Nếu các quyển sách được sắp thành các nhóm: (10,3,2), (4,6,4) và (9) thì khách hàng ấy sẽ được tặng cuốn sách có giá là 2 trong nhóm một, 4 trong nhóm hai, và không có quyển sách nào được tặng trong nhóm ba vì nhóm này chỉ có 1 quyển.

Cô bán hàng là một người tốt bụng vì vậy cô ấy luôn muốn mỗi khách hàng trả ít tiền nhất có thể.

Yêu cầu: Cho giá các quyển sách, hãy giúp cô bán hàng sắp xếp các quyển sách vào các nhóm sao cho tổng số tiền khách hàng phải trả là ít nhất có thể. Chú ý cô bán hàng có thể sắp xếp các quyển sách vào các nhóm có ít nhất 1 quyển hoặc nhiều nhất 3 quyển.

Input

• Dòng 1 gồm một số nguyên \(N (N ≤ 10^5)\) – là số sách khách hàng mua.
• \(N\) dòng tiếp theo mỗi dòng ghi một số nguyên \(A_i (A_i ≤ 10^9)\) – là giá mỗi quyển sách. Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên duy nhất là giá tiền nhỏ nhất mà khách hàng phải trả.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N ≤ 2000\).
• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

4
3
2
3
2 

8

6
6
4
5
5
5
5 

21

Trong nhà Nam hiện đ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_3,…,a_n\) chỗ cắm. 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.

Input

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

Output

• Là 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 đủ, in ra \(−1\).

Example

3 4
3 2 2 

2

4 7
3 3 2 4 

3