Limited Library

Time limit2sMemory limit2048 MB

Summary

Given shelf heights and book heights, place all books on shelves that hold x books each, and find the most shelves that can also hold an art piece taking x-y slots.

Level: Medium6 of 10
Topics: Greedy, Binary search, Sorting
Solved: No attempts yet

Problem

During the summer break, fewer students are on campus, so this is a good time to add new books to the TU Delft library. The new books all have the same width, but their heights vary. Because all existing bookcases are full, the library management board has decided to add a new bookcase to display these books.

The new bookcase has several shelves of varying heights. Each shelf can fit $x$ books. Because there may be leftover space, the board also wants to display some art pieces in this bookcase, at most one per shelf. An art piece fits on a shelf only if at most $y$ books sit next to it, since an art piece takes up the same space as $x-y$ books.

Figure L.1: The hatched areas mark three shelves that have room for an art piece while still holding all the new books.

The management board wants you to find the largest number of shelves on which you can place an art piece while all the new books still fit on the shelves.

Input

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.

Output

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.

Examples4

Example 1
Input
```
4 8 4 2
4 8 6 2
1 2 3 5 7 7 8 8
```
Expected output
```
3
```

Example 2

Input

4 11 3 2
2 2 2 2
1 1 1 1 1 1 1 1 1 1 1

Expected output

Example 3

Input

2 10 3 2
8 6
4 2 1 3 6 2 1 3 4 5

Expected output

impossible

Example 4
Input
```
3 8 8 3
7 9 4
2 3 4 5 6 7 8 9
```
Expected output
```
3
```