모험가 민호는 던전에서 잠겨 있는 보물 상자를 발견했습니다. 이 보물 상자를 열기 위해서는 정확한 비밀번호 조합을 입력해야 합니다.

상자 앞에는 N개의 숫자가 적힌 카드가 놓여 있고, 비밀번호에 대한 힌트로 정수 M이 주어집니다. 상자를 열기 위한 비밀번호의 규칙은 다음과 같습니다.

민호는 고른 3개 카드의 숫자를 모두 더했을 때, M을 넘지 않으면서 M과 가장 가까운 합을 만들어야 합니다.

N개의 카드 숫자가 주어졌을 때, M을 넘지 않으면서 3개의 카드를 골라 만들 수 있는 카드 합의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 카드의 개수 N과 힌트 정수 M이 공백을 사이에 두고 주어진다.

둘째 줄에는 카드에 적혀 있는 수가 N개 주어지며, 각 숫자는 공백으로 구분된다.

출력

첫째 줄에 M을 넘지 않으면서 3개의 카드를 골라 만들 수 있는 합의 최댓값을 출력한다.

제한 사항

• 3 ≤ N ≤ 100

• 10 ≤ M ≤ 300,000

• 카드에 적힌 수는 100,000을 넘지 않는 양의 정수이다.

• 합이 M 이하가 되는 카드 3장의 조합은 반드시 존재한다.

Line 1: \(N\) and \(M\) (\(3 \le N \le 100\), \(10 \le M \le 300000\)). Line 2: \(N\) positive integers, each \(\le 100000\).

Print the largest achievable three-card sum not exceeding \(M\).

riseoj 작성

출처 Online Judge > GoldOJ