파일 압축
시간 제한8초메모리 제한512 MB
압축 전 크기와 압축 후 크기가 주어진 n개의 파일과 여유 공간 m이 있을 때, 묶어서 압축하고 원본을 지우는 과정을 반복해 만들 수 있는 최소 압축 파일 수를 구한다.
문제
여러분의 컴퓨터는 조금 구식이다. CPU는 느리고 메모리는 부족하며 하드 드라이브는 거의 꽉 찼다. 새 컴퓨터를 갖고 싶은 마음은 당연하지만, 안타깝게도 여러분은 그렇게 부유하지 않다. 당분간은 이 낡은 컴퓨터와 함께 살아가야 한다.
지금 당장 임시 조치가 필요한 문제가 하나 있다. 인터넷에서 새 소프트웨어를 내려받았는데 공간이 부족해서 설치하지 못했다. 그래서 기존 파일을 모두 압축 파일로 묶고 원본 압축되지 않은 파일을 모두 지워 하드 드라이브에 공간을 더 확보하기로 했다.
한정된 하드 드라이브 공간 안에서 이 작업을 하려면 조금 복잡하다. 다음 세 단계를 반복해 빈 공간을 만들 계획이다.
- 아직 압축하지 않은 파일 집합을 고른다.
- 고른 파일을 하나의 새 압축 파일로 압축해 하드 드라이브에 저장한다. 이 단계에서는 원본 파일과 압축 파일을 모두 하드 드라이브에 저장할 공간이 필요하다.
- 압축한 파일을 모두 지운다.
단순하게 생각해 어떤 압축 파일도 풀지 않는다. 이 조건에서 압축 파일의 개수를 최대한 줄이고 싶다. 주어진 압축되지 않은 파일 집합마다 압축 파일의 최소 개수를 구하는 프로그램을 작성하라.
입력
입력은 여러 데이터 세트로 이루어진다.
각 데이터 세트의 첫 줄에는 두 정수 n (1 ≤ n ≤ 14)과 m (1 ≤ m ≤ 1000)이 주어진다. n은 파일의 개수, m은 압축 작업을 시작하기 전 하드 드라이브의 사용 가능한 공간이다. 이 줄 다음에는 n개의 줄이 이어지며, 각 줄에는 두 정수 bi와 ai가 주어진다. bi는 i번째 파일의 압축하지 않은 크기, ai는 압축했을 때의 크기이다. 각 압축 파일의 크기는 그 안에 든 파일들의 압축된 크기의 합이다. 1 ≤ i ≤ n인 모든 i에 대해 bi ≥ ai가 성립한다.
두 개의 0이 있는 줄이 입력의 끝을 나타낸다.
출력
각 테스트 케이스마다 압축 파일의 최소 개수를 한 줄에 출력한다. 어떤 방법으로도 모든 파일을 압축할 수 없다면 “Impossible”을 대신 출력한다.