Children and Gift Boxes

Interview

Time limit1sMemory limit1024 MB

Summary

Given N boxes of gifts and M children with desired amounts in a fixed order, decide if each child in turn can take their amount from the currently fullest box.

Level: Medium6 of 10
Topics: Greedy, Heap, Simulation, Sorting
Solved: No attempts yet

Problem

Sanghun has $N$ gift boxes. Each gift box has the number of gifts it currently holds written on it.

There are $M$ children who will receive gifts. Each child is assigned a distinct number from $1$ to $M$ .

One at a time, from child $1$ to child $M$ , each child takes as many gifts as they want from the box that currently holds the most gifts. A child may take from a box that someone has already taken gifts from.

If a box holds fewer gifts than the child wants, the child cannot take any gifts and is disappointed.

Sanghun wants to know whether every child can take the gifts they want without anyone being disappointed.

Input

The first line gives the number of gift boxes $N$ and the number of children $M$ , separated by a space. ( $1\le M \le N\le 10^5$ )

The second line gives the number of gifts in each gift box, $c_1,c_2,\ldots ,c_N$ , separated by spaces. ( $1\le c_i\le 10^5$ )

The third line gives the number of gifts each child wants, $w_1,w_2,\ldots ,w_M$ , in order of the children's numbers, separated by spaces. ( $1\le w_i\le 10^5$ )

Output

Print $1$ if every child can take the gifts they want without anyone being disappointed, and $0$ otherwise.

Examples2

Example 1
Input
```
4 4
4 3 2 1
3 1 2 1
```
Expected output
```
1
```
Example 2
Input
```
4 3
4 3 2 1
3 1 5
```
Expected output
```
0
```