Một nhà máy có n máy có thế được sử dụng để tạo ra sản phẩm. Mục tiêu của bạn là tạo ra tổng số sản phẩm. Đối với mỗi máy, bạn biết số giây nó cần để tạo ra một sản phẩm. Các máy có thể hoạt động đồng thời và bạn có thể tự do quyết định lịch trình của chúng. Thời gian ngân nhất căn thiết để làm ra t sản phẩm là bao nhiêu?

Định dạng đầu vào: Dòng nhập đầu tiên có hai số nguyên n và t: số lượng máy móc và sản phẩm. Dòng tiếp theo ghi n số nguyên k1, k2,..., kn: thời gian cần thiết để tạo ra một sản phẩm sử dụng mỗi máy.

Ràng buộc: 1 <= n <= 2.10^5; 1 <= t <= 10^9; 1 <= ki <= 10^9;

Định dạng đầu ra: In một số nguyên: thời gian tối thiểu cần thiết để tạo ra t sản phẩm.

Input:

3 7
3 2 5

Output:

8

Giải thích: Trong 8s, máy 1 làm được 2 sản phẩm, máy 2 làm được 4 sản phẩm, máy 3 làm được 1 sản phẩm.

Một dãy số được gọi là dạng đỉnh núi nếu nó tăng dần đến một vị trí rồi giảm dần. Hãy tìm chỉ số của phần tử lớn nhất (đỉnh núi) trong dãy. (Dữ liệu đảm bảo dãy có dạng đỉnh núi).

Dữ liệu vào:

Dòng 1: N.

Dòng 2: Dãy số.

Dữ liệu ra:

Chỉ số của đỉnh (tính từ 1).

Ràng buộc:

3 <= N <= 10^5

Ví dụ:

Input:

5 
1 3 5 4 2

Output:

3

Có N cái chuồng nằm trên một đường thẳng tại các vị trí x1, x2, ..., xN. Cần xếp C con bò vào các chuồng sao cho khoảng cách nhỏ nhất giữa 2 con bò bất kỳ là lớn nhất có thể.

Dữ liệu vào:

Dòng 1: N và C.

Dòng 2: N vị trí của các chuồng (chưa chắc đã sắp xếp).

Dữ liệu ra:

Khoảng cách lớn nhất tìm được.

Ràng buộc:

2 <= C <= N <= 10^5

0 <= xi <= 10^9

Ví dụ:

Input:

5 3 
1 2 8 4 9

Output:

3

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

Cho một bảng số kích thước NxN, trong đó phần tử ở hàng i, cột j có giá trị là i * j. Hãy tìm số nhỏ thứ K trong bảng này nếu ta trải phẳng bảng ra và sắp xếp lại.

Dữ liệu vào:

Hai số N và K.

Dữ liệu ra:

Số nhỏ thứ K.

Ràng buộc:

1 <= N <= 10^5

1 <= K <= N*N

Ví dụ:

Input:

3 7

Output:

6

Bạn có số tiền M. Có N cuốn sách với giá A[1], A[2],... Bạn muốn mua nhiều cuốn sách nhất có thể sao cho tổng giá tiền không vượt quá M. (Lưu ý: Dãy A chưa sắp xếp, bạn cần sắp xếp rồi dùng Tiền tố hoặc Binary Search, nhưng bài này ta dùng Binary Search trên kết quả số lượng sách K). Dữ liệu vào:

Dòng 1: N và M.

Dòng 2: Giá các cuốn sách.

Dữ liệu ra:

Số lượng sách tối đa mua được.

Ràng buộc:

1 <= N <= 10^5

1 <= M <= 10^14

Ví dụ:

Input:

5 10 
2 4 3 5 1

Output:

4

Nhà An có N cái cây, cây thứ i có chiều cao ban đầu là A[i] cm. An vừa mua được M lọ thuốc tăng trưởng cực tốc. Mỗi lọ thuốc khi tưới vào một cái cây bất kỳ sẽ giúp cây đó cao thêm đúng 1 cm ngay lập tức (một cây có thể được tưới nhiều lọ thuốc).

An muốn sử dụng M lọ thuốc này một cách hợp lý nhất để chiều cao của cái cây thấp nhất trong vườn là cao nhất có thể.

Yêu cầu: Hãy tính chiều cao của cái cây thấp nhất sau khi An đã sử dụng tối ưu toàn bộ M lọ thuốc.

Dữ liệu vào: Đọc từ thiết bị chuẩn (bàn phím)

Dòng đầu tiên chứa hai số nguyên dương N và M (1 <= N <= 10^5, 0 <= M <= 10^9).

Dòng thứ hai chứa N số nguyên biểu diễn chiều cao ban đầu của các cây A[1], A[2], ..., A[N] (0 <= A[i] <= 10^9).

Dữ liệu ra: Ghi ra thiết bị chuẩn (màn hình)

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

Input:

3 4 
2 4 6

Output:

5

Giải thích ví dụ:

Có 3 cây với chiều cao lần lượt là 2, 4, 6. An có 4 lọ thuốc.

Phương án tối ưu:

Dùng 3 lọ thuốc cho cây thứ nhất: Chiều cao từ 2 -> 5.

Dùng 1 lọ thuốc cho cây thứ hai: Chiều cao từ 4 -> 5.

Cây thứ ba không dùng thuốc: Chiều cao giữ nguyên là 6.

Sau khi dùng hết 4 lọ thuốc, chiều cao của các cây là: 5, 5, 6. Cái cây thấp nhất trong vườn lúc này cao 5cm. Đây là kết quả tối ưu nhất.

Cho dãy A đã sắp xếp tăng dần. Hãy đếm xem số X xuất hiện bao nhiêu lần trong dãy.

Dữ liệu vào:

Dòng 1: N và X.

Dòng 2: N số nguyên dãy A.

Dữ liệu ra:

Số lần xuất hiện của X.

Ràng buộc:

1 <= N <= 10^5

|A[i]|, |X| <= 10^9

Ví dụ:

Input:

7 2 
1 1 2 2 2 3 4

Output:

3