Tí có một số tiền là M đồng. Cửa hàng đồ chơi có N món đồ, món thứ i có giá là A[i]. Tí muốn mua được nhiều món đồ nhất có thể với số tiền M. Hãy tính xem Tí có thể mua được tối đa bao nhiêu món đồ.

Dữ liệu vào:

Dòng đầu tiên chứa hai số N và M.

Dòng thứ hai chứa N số nguyên A[i] là giá của các món đồ chơi.

Dữ liệu ra:

Số lượng món đồ tối đa Tí có thể mua.

Giới hạn:

1 <= N <= 10^5

1 <= M <= 10^14

1 <= A[i] <= 10^9

Ví dụ 1:

Input:

5 10 
3 1 4 2 5

Output:

4

Ví dụ 2:

Input:

3 5 
10 20 30

Output: 0

Số trung vị của một dãy số là số nằm ở chính giữa dãy số đó sau khi đã được sắp xếp tăng dần. Cho N là một số lẻ, hãy tìm số trung vị của dãy số.

Đầu vào:

Dòng 1: Số nguyên dương lẻ N.

Dòng 2: N số nguyên.

Đầu ra:

Số trung vị tìm được.

Ràng buộc:

1 <= N <= 999 (N luôn là số lẻ)

0 <= A[i] <= 10^9

Ví dụ 1:

Input:

5 
10 2 8 4 6

Output:

6

(Giải thích: Dãy sắp xếp là 2 4 6 8 10, số ở giữa là 6)

Ví dụ 2:

Input:

3 
100 1 50

Output:

50

Lớp học của HCN gồm có n học sinh. HCN cầm một danh sách bao gồm tên, ngày sinh và điểm trung bình của các bạn trong lớp. Là lớp trưởng, HCN được giáo viên tín nhiệm giao công việc sắp xếp điểm các bạn theo thứ tự, Tuy nhiên, bạn đã biết HCN chăm chỉ thế nào, nên đã tự giác đi làm thay bạn ý luôn...

Đầu vào:

• Dòng đầu tiên chứa số nguyên dương n - số lượng học sinh trong lớp HCN (n ≤ 60).

• n dòng tiếp theo, môi dòng chứa ba thông tin: Tên (không dấu), ngày sinh và điếm trung bình (là một số thực không vượt quá 10).

• Dữ liệu đám bảo không có 2 bạn nào cùng điểm.

Đầu ra: Gồm n dòng, theo thứ tự điểm từ thấp nhất đến cao nhất, gồm tên và điểm của từng học sinh (cách nhau một khoảng trắng).

Input:

3
Lan 18/9/2006 8.8
An 11/3/2006 9.1
TDZ 10/12/2006 8.0

Output:

TDZ 8.0
Lan 8.8
An 9.1

Được nghỉ hè nhưng không biết làm gì, HCN liền lên ý tưởng lập một hiệu sách dạo ngoài đường.

HCN dự định bán n quyển sách cũ của mình, quyển sách thứ i có giá là c. Tuy nhiên, sợ do ế khách, HCN đề ra một chương trình ưu đãi "mua 3, tặng 1".

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 đó. Mỗi khách hàng có thể mua bao nhiêu sách cũng được và có thể trả số tiền khác nhau phụ thuộc vào việc chọn các nhóm bộ ba sách.

Ví dụ, một 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.

Hãy giúp HCN tính số tiền ít nhất có thể thu được khi bán hết n quyển sách đó, vì cậu trốn quá nhiều tiết Toán rồi...

Input:

• Dòng đầu tiên chưa số nguyên dương n (n ≤ 10^5).

• Dòng tiếp theo chứa n số nguyên dương c1, c2, c3, ..., cn tương ứng với giá tiền mỗi quyển sách (c ≤ 10^5).

Output:

In ra số tiền thu được ít nhất có thể khi bán hết n quyến sách.

Input:

4
3 2 3 2

Output:

8

Input:

6
6 4 5 5 5 5

Output:

21

Bạn được cho một mảng gồm n số nguyên và số nguyên k. Thuật toán Bubble Sort sẽ duyệt mảng từ trái sang phải trong từng vòng, hoán đổi các cặp phần tử liền kề nếu chúng nằm sai thứ tự.

Nhiệm vụ của bạn là tìm ra trạng thái của mảng sau k vòng lặp.

Dữ liệu vào:

Dòng 1: Hai số nguyên n và k — kích thước mảng và số vòng bubble sort cần thực hiện.

Dòng 2: n số nguyên x₁, x₂, …, xₙ — các phần tử của mảng.

Dữ liệu ra:

In ra n số nguyên: trạng thái của mảng sau k vòng bubble sort.

Ràng buộc:

~1 \le n \le 2 \cdot 10^5~

~0 \le k \le 10^9~

~1 \le x_i \le 10^9~

Ví dụ :

Input:

5 2
3 2 4 1 4

Output:

2 1 3 4 4

Có N máy sản xuất. Máy thứ i cần T[i] giây để tạo ra 1 sản phẩm. Các máy hoạt động song song. Hỏi cần ít nhất bao nhiêu giây để tạo ra tổng cộng K sản phẩm?

Dữ liệu vào:

Dòng 1: N và K.

Dòng 2: Thời gian T[i] của các máy.

Dữ liệu ra:

Thời gian ít nhất.

Ràng buộc:

1 <= N <= 10^5

1 <= K <= 10^9

1 <= T[i] <= 10^9

Ví dụ:

Input:

3 7 
3 2 5

Output:

8

Cho dãy A gồm N phần tử đã sắp xếp tăng dần và số nguyên K. Hãy đếm số cặp (i, j) sao cho i < j và A[i] + A[j] = K. (Sử dụng tìm kiếm nhị phân cho mỗi A[i]).

Dữ liệu vào:

Dòng 1: N và K.

Dòng 2: Dãy A.

Dữ liệu ra:

Số lượng cặp thỏa mãn.

Ràng buộc:

1 <= N <= 10^5

|A[i]| <= 10^9

Ví dụ:

Input:

5 9 
1 3 5 6 8

Output:

2

Cho một dãy số gồm N phần tử là một cấp số cộng (tăng dần) nhưng bị thiếu mất đúng 1 số. Hãy tìm số đó. (Gợi ý: Dùng tìm kiếm nhị phân dựa trên sự chênh lệch giữa giá trị thực tế và giá trị kỳ vọng).

Dữ liệu vào:

Dòng 1: N (Số lượng phần tử hiện có).

Dòng 2: Dãy số.

Dữ liệu ra:

Số bị thiếu.

Ràng buộc:

2 <= N <= 10^5

Ví dụ:

Input:

4 
2 4 8 10

Output:

6