| The Club Ballroom |
A social club is building its new ballroom. The club members wish to have the floor covered with wood planks, as they consider this to be the best for dancing. A lumberyard from the region donated a large quantity of good quality wooden planks to be used in the ballroom. The donated planks have all the same width, but have different lengths.
The ballroom is a rectangle of dimensions N x M meters. The planks must be placed, so that no plank overlaps another, and the whole floor must be covered. They must be aligned, lengthwise, to one of the sides of the ballroom, and all planks must be parallel. The club members do not want too many joints in the floor, and therefore if a plank is not long enough to cover the distance between two opposite sides of the ballroom, it can be joined to at most one other plank to complete the distance. Furthermore, the chief-carpenter has a great respect for all woods, and would rather not saw any plank. Therefore, he wants to know whether it is possible to cover the floor with the set of planks donated, observing the restrictions described; in case it is possible, the chief-carpenter wish to know the smallest number of planks he can use.
The figure below depicts two possible ways to cover the floor of a ballroom with dimensions 4 x 5 meters for a set of ten donated planks, with 100 cm width, and lengths 1, 2, 2, 2, 2, 3, 3, 4, 4 and 5 meters.
The input contains several test cases. The first line of a test case contains two integers N and M indicating the dimensions, in meters, of the ballroom (1 ≤ N,M ≤ 104). The second line contains one integer L representing the planks width, in centimeters (1 ≤ L ≤ 100). The third line contains one integer K, indicating the number of planks donated (1 ≤ K ≤ 105). The fourth line contains K integers Xi, separated by spaces, representing the length, in meters, of one plank (1 ≤ Xi ≤ 104 for 1 ≤ i ≤ K). The end of the input is indicated by a line containing only two zeros, separated by one space.
For each of the test cases in the input your program must print one single line, containing one integer, the smallest number of planks needed to cover the whole floor, satisfying the restrictions established. If it is not possible to cover the whole floor satisfying the restrictions established, print one line with the word "impossivel" (which means impossible in Portuguese).
4 5 100 10 1 2 2 2 2 3 3 4 4 5 5 4 100 7 4 5 4 4 4 4 3 4 5 99 4 4 4 4 4 3 2 100 7 2 4 1 4 2 4 4 0 0
7 5 impossivel impossivel