만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

두 선물

면접 대비

시간 제한1초메모리 제한1024 MB

요약
n개의 선물 가격과 예산 x가 주어질 때, 서로 다른 두 선물의 가격 합이 x를 넘지 않으면서 최대가 되는 값을 구합니다.
난이도

쉬움10점 중 3점

유형
투 포인터, 정렬
정답자
아직 제출이 없습니다

문제

세냐는 새해 선물을 고르고 있다. 산타클로스(데드 모로즈)는 정확히 두 개의 선물을 사는데, 하나는 엄마가, 다른 하나는 아빠가 준 것처럼 보이게 한다.

가게에는 nn개의 선물이 있고, ii번째 선물의 가격은 aia_i루블이다. 산타클로스는 두 선물에 최대 xx루블까지 쓸 수 있다. 세냐는 가능한 한 비싼 선물을 받고 싶어 하므로, 서로 다른 선물 두 개를 골라 가격의 합이 xx를 넘지 않으면서 최대가 되도록 해야 한다.

세냐가 선물을 고르는 것을 도와라.

입력

첫 줄에 정수 nn과 xx가 주어진다 (2≤n≤1000002 \le n \le 100000, 2≤x≤1092 \le x \le 10^9). 둘째 줄에 정수 a1,a2,…,ana_1, a_2, \ldots, a_n이 주어진다 (1≤ai≤1091 \le a_i \le 10^9). 가격의 합이 xx 이하인 선물 두 개가 항상 존재한다.

출력

서로 다른 선물 두 개의 가격 합 중 xx를 넘지 않는 최댓값을 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    6 18
    5 3 10 2 4 9
    
    예상 출력
    15