Số vé cần đổi (Additional Tickets Required)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có n lô vé, lô thứ i gồm a_i vé. Cần ít nhất T vé. Một thao tác tăng số vé lên đúng một. Hãy tính số thao tác ít nhất để tổng vé đạt hoặc vượt T. Nếu tổng đã đủ, kết quả bằng 0. Không giới hạn số thao tác có thể thực hiện.

Input

Dòng đầu gồm n T. Sau đó có đúng n số nguyên không âm a_i.

Output

In một số nguyên không âm là số thao tác nhỏ nhất.

Subtask

• Subtask 1 (20%): 0 ≤ n ≤ 10, 0 ≤ T ≤ 100, 0 ≤ a_i ≤ 100.

• Subtask 2 (30%): 0 ≤ n ≤ 1000, 0 ≤ T ≤ 100000, 0 ≤ a_i ≤ 100000.

• Subtask 3 (50%): 0 ≤ n ≤ 100000, 0 ≤ T ≤ 10^9, 0 ≤ a_i ≤ 100000.

Ví dụ

Ví dụ 1

Input:

3 15
3 4 2

Output:

6

Giải thích: Ban đầu có 9 vé; cần tăng thêm 6 vé.

Ví dụ 2

Input:

2 10
5 6

Output:

0

Giải thích: Đã có 11 vé nên không cần thao tác nào.

Ví dụ 3

Input:

0 3

Output:

3

Giải thích: Không có vé ban đầu; tăng 3 lần.