#321 Maximum Remaining Money After Buying Gifts

Companies:

Unknown company

Themes:

AlgorithmsBinary SearchPractice

Maxim has a prepared list of n gifts. He plans to go through the list in order, and every time he sees a gift he can afford, he must buy it immediately.

Help him calculate the maximum amount of money he can have left after buying gifts if he takes a loan of the optimal size, meaning a loan that leaves him with as much money as possible after following the purchasing algorithm.

Input format:

The first line contains two integers n and m (1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^9) — the length of the gift list and the size of the pre-approved loan.

The second line contains n integers — the gift prices a[i] (≤ a[i] ≤ 10^9).

Output format:

Print one number — the maximum number of burles that Maxim could have left after buying the gifts.

Note 1:

In the first example, Maxim can borrow 3 burles, and then he will buy only the last gift. In the second example, Maxim can take the full 10-burle loan and buy all the gifts.

Example 1:

Input: 3 10 5 4 1
Output: 2

Example 2:

Input: 3 10 1 2 3
Output: 4

Question review

Mentor

Answer as you would in a real interview. I’ll ask follow-up questions, then compare your answer with the reference answer and show your accuracy as a %.

Sign in to start the dialogue The mentor keeps the context of the current question and your previous messages.