Picky Children and Gift Boxes

Interview

Time limit1sMemory limit1024 MB

Summary

Each child in order takes w_i gifts from the box ranked b_i-th largest by current count; decide if every child can succeed.

Level: Medium6 of 10
Topics: Sorting, Greedy, Array, Implementation
Solved: No attempts yet

Problem

Sanghun has $N$ gift boxes. Each gift box is labeled with the number of gifts it currently contains.

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

Children $1$ through $M$ , one at a time, each take as many gifts as they want from the gift box that has the $b_i$ -th most gifts, where $b_i$ is that child's thoughtfulness. For example, if a child's thoughtfulness is $3$ , they take from the box with the third most gifts. A child may take from a box that someone has already taken gifts from.

However, if the box contains 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$ )

The fourth line gives each child's thoughtfulness, $b_1, b_2, \ldots ,b_M$ , in order of the children's numbers, separated by spaces. ( $1\le b_i\le N$ )

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
2 1 4 3
3 1 2 1
1 1 3 2
```
Expected output
```
0
```
Example 2
Input
```
4 3
4 3 2 1
3 1 2
1 3 2
```
Expected output
```
1
```