문제 AM: [2023 충북정올 예선(중등부) 3번] 공성전

문제 AM: [2023 충북정올 예선(중등부) 3번] 공성전

[만든사람 : ]
시간제한 : 1.000 sec  메모리제한 : 128 MB

제출문제리스트

문제 설명

흑우나라는 좋은 관계를 유지하기 위해 강대국인 올림피아드나라에 매년 공물을 바치고 있었다. 그런데 갑자기 앞으로는 매년 보내던 공물의 2배를 바치라는 것이었다. 이러한 요구를 받아들일 수 없다고 생각한 흑우나라는 올림피아드나라의 성들을 공격하기로 했다.

올림피아드 나라의 성들은 높은 성벽 때문에 일반적인 공성전으로는 이길 가능성이 매우 낮았다. 그리하여 특별부대가 야간에 몰래 성벽을 넘어 성문을 열어주면 전 병력이 공격하는 작전을 세웠다.

성벽을 넘기 위해서는 성벽 높이 H (1 ≤ H ≤ 1000) 이상의 사다리가 필요하다. 흑우나라는 그렇게 긴 사다리가 없으므로 조립식 사다리 N (1 ≤ N ≤ 20)개를 준비하였는데 각 사다리의 길이는 Li (1 ≤ Li ≤ 1,000)의 길이를 가진다.

주어진 성벽 높이보다 조립식 사다리를 연결한 길이가 짧으면 성벽을 넘을 수 없으나 연결한 사다리의 높이가 성벽 높이 이상일 때는 성벽을 넘을 수 있다. 성벽의 높이와 조립한 사다리 길이 차이가 최소가 되는 길이가 얼마인지 구하시오.
단, 모든 경우에서 조립한 사다리의 길이는 성벽 높이 이상으로 성벽을 무조건 넘을 수 있다고 가정한다.

입력 설명

첫 번째 줄에는 자연수 N, H가 주어진다. (1 ≤ N ≤ 20, 1 ≤ H ≤ 1000)
다음 N개의 줄에는 L(1 ≤ Li ≤ 1,000) 가 각 줄마다 주어진다.

출력 설명

성벽의 높이와 조립한 사다리 길이 차이가 최소가 되는 길이를 자연수 형태로 출력하시오.
단, 모든 경우에서 조립한 사다리의 길이는 성벽 높이 이상으로 성벽을 무조건 넘을 수 있다고 가정한다.

입력 예시 Copy

3 3
1
2
3

출력 예시 Copy

0