비트토렌트

비트토렌트는 큰 파일을 주고받는 P2P 프로토콜이다. 중앙 서버가 자원을 내려 주고 클라이언트는 요청만 하는 집중형 구조와 달리, 여기서는 모든 노드가 클라이언트 역할과 서버 역할을 동시에 맡는다. 참여자는 호스트 여러 대로 그룹을 만들어, 서로에게서 파일을 내려받으면서 동시에 서로에게 올린다.

토렌트라고 부르는 파일 묶음 전체는 그림처럼 조각으로 잘린다. 10MB 묶음이라면 1MB 조각 열 개로 자를 수도 있고, 256KB 조각 마흔 개로 자를 수도 있다. 호스트는 새 조각을 받는 순간 그 조각을 원하는 다른 호스트에게 그 조각을 내주는 공급원이 된다. 조각은 보통 순서와 상관없이 도착하고, 호스트가 원래 순서대로 다시 배열한다. 어떤 조각을 받을지는 호스트마다 스스로 정한다. 한 토렌트 안에서 조각 크기는 모두 같으며, 마지막 조각만 더 작을 수 있다.

파일 묶음을 내려받고 싶은데 이번 달 인터넷 사용량 한도가 얼마 남지 않았고, 다음 달까지 기다릴 생각은 없다. 남은 전송량으로 온전한 파일을 최대한 많이 확보하려고 한다.

조각은 쪼갤 수 없어서 받으려면 한 조각을 통째로 받아야 한다. 파일 하나를 얻으려면 그 파일의 일부라도 들어 있는 조각을 모두 받아야 하고, 한 조각을 여러 파일이 나눠 쓰고 있으면 그 조각은 한 번만 받으면 된다. 파일은 입력에 주어진 순서대로 이어 붙인 다음 앞에서부터 $P$ KB씩 잘라 조각으로 나눈다.

남은 전송량으로 온전히 받을 수 있는 파일의 최대 개수를 구하라.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 정수 $N$, $P$, $L$이 공백을 두고 주어진다. $N$은 토렌트에 담긴 파일의 개수 ($1 \le N \le 3000$), $P$는 조각 하나의 크기 (KB 단위, $1 \le P \le 1000$), $L$은 이번 달 인터넷 사용량 한도에서 남은 용량 (KB 단위, $1 \le L \le 10^6$)이다. 둘째 줄에는 100,000 이하의 양의 정수 $N$개가 공백을 두고 주어지며, $i$번째 수는 토렌트의 $i$번째 파일 크기(KB)이다. 입력의 마지막 줄은 0 0 0이고, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 남은 용량으로 온전히 받을 수 있는 파일의 최대 개수를 한 줄에 출력한다. 온전히 받을 수 있는 파일이 하나도 없으면 0을 출력한다.