Additional Tickets Required

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

You have n batches of tickets with a_i tickets each. One operation adds exactly one ticket. Find the minimum operations needed so the total reaches at least T; print 0 if already sufficient.

Input

First n T, followed by exactly n nonnegative counts a_i.

Output

Print the minimum nonnegative number of operations.

Subtasks

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

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

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

Examples

Example 1

Input:

3 15
3 4 2

Output:

6

Explanation: Initially there are 9 tickets; 6 more are required.

Example 2

Input:

2 10
5 6

Output:

0

Explanation: 11 tickets already meet the threshold 10.

Example 3

Input:

0 3

Output:

3

Explanation: No tickets initially, so add 3.