두 선물
면접 대비시간 제한1초메모리 제한1024 MB
n개의 선물 가격과 예산 x가 주어질 때, 서로 다른 두 선물의 가격 합이 x를 넘지 않으면서 최대가 되는 값을 구합니다.
문제
세냐는 새해 선물을 고르고 있다. 산타클로스(데드 모로즈)는 정확히 두 개의 선물을 사는데, 하나는 엄마가, 다른 하나는 아빠가 준 것처럼 보이게 한다.
가게에는 개의 선물이 있고, 번째 선물의 가격은 루블이다. 산타클로스는 두 선물에 최대 루블까지 쓸 수 있다. 세냐는 가능한 한 비싼 선물을 받고 싶어 하므로, 서로 다른 선물 두 개를 골라 가격의 합이 를 넘지 않으면서 최대가 되도록 해야 한다.
세냐가 선물을 고르는 것을 도와라.
입력
첫 줄에 정수 과 가 주어진다 (, ). 둘째 줄에 정수 이 주어진다 (). 가격의 합이 이하인 선물 두 개가 항상 존재한다.
출력
서로 다른 선물 두 개의 가격 합 중 를 넘지 않는 최댓값을 한 줄에 출력한다.