1703 - 111qqz's games on steam
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 20
Solved: 7
- Description
On Steam( a famous game platform) recently a new collection of games went on sale. This collection consists of as many as 1E9 types of games, numbered with integers 1..1E9. A game from the new collection of the i-th type costs i dollars
111qqz has managed to collect n different types of games a1, a2, ..., an from the new collection.
Today 111qqz is not happy,because she didn’t code well in the last round of the codeforces(http://codeforces.com/) contest .So she decided to spend no more than m dollars to make herself happy. 111qqz will choose several different types of games from the new collection . Of course, she does not want to get a type of game which she already has.
111qqz wants to have as many distinct types of games in her collection as possible as the result. The new collection is too diverse, and 111qqz is too stupid, so she asks you to help her in this.
- Input
The first line contains two integers n (1 ≤ n ≤ 1 000 000) and m (1 ≤ m ≤ 109) — the number of types of games that 111qqz already has and the number of dollars that her is willing to spend on buying new games on Steam.
The next line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the types of games that 111qqz already has.
- Output
Print a single integer k — the number of different types of games that 111qqz should choose so that the number of different types of games in her collection is maximum possible. Of course, the total cost of the selected games should not exceed m.
- sample input
-
4 14 4 6 12 8
- sample output
-
4
- hint
- source
- 111qqz