레이팅 미적용During the summer break, fewer students are dwelling on campus, so this is the perfect time to add new books to the TU Delft library. These new books all have the same width, but they have varying heights. Because all existing bookcases are already full, the management board of the library has decided that they will add a new bookcase to display these new books.
The new bookcase has a number of shelves with varying heights. Each shelf in the bookcase can fit \(x\) books. Since there may be some leftover space, the management board would also like to display some art pieces in this bookcase, at most one per shelf. An art piece will only fit on a shelf if there are at most \(y\) books next to it, because the art pieces take up the same amount of space as \(x-y\) books. As an example, Figure shows a bookcase where three of the shelves have enough space for an art piece.
The management board wants you to find the largest number of shelves on which you can place an art piece, whilst also being able to fit all the new books on the shelves.
The input consists of:
- One line with four integers \(n\), \(m\), \(x\), and \(y\) ($1 \leq n, m \leq
10^5\(, \)1 \leq y < x \leq 1000$), the number of shelves, the number of books, the number of books that fit on a full shelf, and the number of books that fit on a shelf next to an art piece.
- One line with \(n\) integers \(a\) (\(1 \leq a \leq 10^9\)), the heights of the shelves.
- One line with \(m\) integers \(b\) (\(1 \leq b \leq 10^9\)), the heights of the books.
If it is possible to fit all the \(m\) books into the \(n\) shelves, output the largest number of art pieces you can place. Otherwise, output "impossible".
4 8 4 2
4 8 6 2
1 2 3 5 7 7 8 8
3
4 11 3 2
2 2 2 2
1 1 1 1 1 1 1 1 1 1 1
1
2 10 3 2
8 6
4 2 1 3 6 2 1 3 4 5
impossible
3 8 8 3
7 9 4
2 3 4 5 6 7 8 9
3