클럽 홀

칭구아 레크리에이션 클럽이 새 회관을 짓고 있다. 회원들은 회관 홀 바닥을 나무 판자로 깔기를 원한다. 클럽의 유명한 무도회에는 판자 바닥이 가장 좋다고 생각하기 때문이다. 이 지역의 한 목재소가 바닥에 쓸 품질 좋은 판자를 많이 기증했다. 기증된 판자는 모두 폭이 같지만 길이는 서로 다르다.

홀 바닥은 직사각형이다. 판자는 서로 겹치는 부분 없이 나란히 붙여 놓아야 하며, 홀 바닥 전체를 덮어야 한다. 판자는 길이 방향으로 줄을 맞추어 놓아야 하고 모두 같은 방향이어야 한다. 즉 모든 판자는 길이 방향으로 서로 평행하다. 또한 회원들은 바닥에 이음매가 많은 것을 원하지 않는다. 그래서 판자 하나가 홀의 한쪽 벽에서 반대쪽 벽까지 닿을 만큼 길지 않으면, 그 판자는 다른 판자 최대 한 개와 이어 붙여 거리를 채울 수 있다. 따라서 판자 한 줄은 길이가 홀의 한 변과 같은 판자 한 개이거나, 길이의 합이 그 변과 같은 판자 두 개로 이루어진다.

그런데 문제가 하나 더 있다. 목수 반장은 모든 목재를 매우 아끼기 때문에 어떤 판자도 톱으로 자르지 않으려 한다. 그래서 목수 반장은 기증된 판자로 위의 조건을 지키면서 바닥 전체를 덮을 수 있는지 알고 싶어 한다. 덮을 수 있다면 필요한 판자의 최소 개수도 알고 싶어 한다.

아래 그림은 폭이 100 cm이고 길이가 1, 2, 2, 2, 2, 3, 3, 4, 4, 5미터인 판자 10개로 4 × 5미터 홀 바닥을 덮는 두 가지 방법을 보여 준다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 홀의 크기를 미터 단위로 나타내는 두 정수 $M$과 $N$이 주어진다 ($1 \le N, M \le 10^4$). 둘째 줄에는 판자의 폭을 센티미터 단위로 나타내는 정수 $L$이 주어진다 ($1 \le L \le 100$). 셋째 줄에는 기증된 판자의 개수를 나타내는 정수 $K$가 주어진다 ($1 \le K \le 10^5$). 넷째 줄에는 판자 하나하나의 길이를 미터 단위로 나타내는 정수 $X_i$ $K$개가 공백 하나로 구분되어 주어진다 ($1 \le i \le K$일 때 $1 \le X_i \le 10^4$).

입력의 끝은 0 두 개가 공백 하나로 구분되어 있는 줄로 나타낸다.

각 테스트 케이스마다 조건을 지키면서 홀 바닥 전체를 덮는 데 필요한 판자의 최소 개수를 한 줄에 출력한다. 조건을 지키면서 바닥 전체를 덮을 수 없으면 impossivel(모두 소문자, 악센트 없음)을 한 줄에 출력한다.