Under construction

Still being built. Things may change

Two Gifts

Interview

Time limit1sMemory limit1024 MB

Summary
Given n gift prices and a budget x, find the largest sum of two different gifts that does not exceed x.
Level

Easy3 of 10

Topics
Two pointers, Sorting
Solved
No attempts yet

문제

Senya is choosing New Year gifts. Ded Moroz will buy him exactly two gifts, one that is supposedly from his mom and another that is supposedly from his dad.

The store sells nn gifts, and the price of the ii-th gift is aia_i rubles. Ded Moroz can spend at most xx rubles on the two gifts. Senya wants the most expensive pair possible, so he needs to choose two different gifts with the maximum total price that does not exceed xx.

Help Senya choose his gifts.

입력

The first line contains two integers nn and xx (2≤n≤1000002 \le n \le 100000, 2≤x≤1092 \le x \le 10^9). The second line contains nn integers a1,a2,…,ana_1, a_2, \ldots, a_n (1≤ai≤1091 \le a_i \le 10^9). It is guaranteed that there are two gifts whose total price does not exceed xx.

출력

Print one integer: the maximum total price of two different gifts that does not exceed xx.

Examples1

  1. Example 1

    Input
    6 18
    5 3 10 2 4 9
    
    Expected output
    15