题目描述

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.

:::align{center}

The many bookshelves in the TU Delft library.

:::

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 L.1 shows a bookcase where three of the shelves have enough space for an art piece.

:::align{center}

Figure L.1: Illustration of Sample Input 1. Three shelves can have art pieces in the hatched areas, while still fitting all new books.

:::

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 "$\texttt{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