문제
철수는 친구의 결혼식에 참석했다가 식이 끝난 후 뷔페에서 음식을 먹으려고 한다.
뷔페에는 N가지의 음식이 준비되어 있지만 철수는 지금 다이어트 중이라서 음식을 너무 많이 먹으면 안 되기 때문에 4개 이하로만 먹으려고 한다. 서로 다른 4가지 음식을 각각 1개씩 먹어도 되지만 같은 음식 4개를 먹어도 된다. 물론 4개를 모두 먹지 않고 1~3개만 먹어도 된다.
또한 음식의 개수뿐 아니라 칼로리도 최소한으로 줄여서 먹어야 한다. 하지만 철수가 먹은 칼로리의 합이 M보다 작으면 영양실조로 병원 신세를 져야만 한다.
각 음식들의 칼로리와 철수가 먹어야 하는 최소한의 칼로리 M이 주어질 때 철수가 먹을 수 있는 칼로리의 최소값을 구하는 프로그램을 작성하시오.
입력
첫 행에 음식의 종류 N과 최소한의 칼로리 M이 자연수로 주어진다.( 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000,000)두 번째 행부터 N개의 행에 걸쳐 각 음식의 칼로리가 주어진다. (1이상 100,000,000이하의 자연수)
<제약조건1> 데이터의 30%는 N ≤ 100 이다. <제약조건2> 데이터의 50%는 N ≤ 300 이다.
출력
철수가 먹을 수 있는 M보다 큰 칼로리의 최소값을 출력한다. 불가능한 경우는 없다.
예제
5 50
23
14
15
59
31
51
힌트
출처
kyio2013(성결대)
로그인해야 코드를 작성할 수 있어요.