아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Два подарка

면접 대비

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

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

보통10점 중 4점

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

문제

Сеня выбирает себе подарки на новый год. Он знает, что Дед Мороз купит ему ровно два подарка: один якобы от мамы, а другой якобы от папы.

В магазине, где Дед Мороз будет покупать подарки, продаётся nn подарков, про каждый подарок известна его цена: цена ii-го подарка равна a_ia\_i рублей. Сеня знает, что Дед Мороз может потратить на покупку его подарков не больше xx рублей. Разумеется, он хочет получить как можно более дорогие подарки. Таким образом, он хочет выбрать два различных подарка с максимальной суммарной ценой, но при этом она не должна превышать xx.

Помогите Сене выбрать себе подарки.

입력

Первая строка ввода содержит два целых числа: nn и xx (2≤n≤100,0002 \le n \le 100\\,000, 2≤x≤1092 \le x \le 10^9). Вторая строка ввода содержит nn целых чисел: a_1,a_2,…,a_na\_1, a\_2, \ldots, a\_n (1≤a_i≤1091 \le a\_i \le 10^9). Гарантируется, что существует два подарка с суммарной ценой не больше xx.

출력

Выведите одно целое число: максимальную суммарную цену двух различных подарков, не превышающую xx.

예제1

  1. 예제 1

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