Competitions
Техника двух указателей
The best team
n programmers gathered today. Every programmer has a rating showing his strength. Rating is an integer from 0 to 10^9
. Your rating as a programmer is m. From all the programmers gathered today, you want to choose two for your team. They should be chosen so that the sum of their ratings is maximum, but this sum should not exceed your rating, since you want to be the head of this team.
Input data
The first line contains two integers: n (2 ≤ n ≤ 10^5
) - the number of programmers and m (0 ≤ m ≤ 10^9
) - your rating. The second line contains n integers r[1]
, r[2]
, ... ,r[n]
(0 ≤ r[i]
≤ 10^9
), the ratings of programmers.
Output data
Print one integer - the sum of the ratings of the selected programmers, or -1 if it is impossible to find such two people.
Examples
Input example #1
5 8 5 3 4 6 5
Output example #1
8
Input example #2
7 19 8 4 25 1 20 5 12
Output example #2
17
Input example #3
4 76 38 41 39 40
Output example #3
-1