Treasure Map

Mr. Kobou found a bundle of old paper when he was cleaning his family home. On each paper, two series of numbers are written. Strange as it appeared to him, Mr. Kobou further went through the storehouse and found out a note his ancestor left. According to it, the bundle of paper is a treasure map, in which the two sequences of numbers seem to give a clue to the whereabouts of the treasure the ancestor buried.

Mr. Kobou’s ancestor divided the area where he buried his treasure in a reticular pattern and used only some of the grid sections. The two series of numbers indicate the locations: the $i$-th member of the first series indicates the number of locations in the $i$-th column (form left) of the grid sections where a part of the treasure is buried, and the $j$-th member of the second indicates the same information regarding the $j$-th row from the top. No more than one piece of treasure is buried in one grid section. An example of a 5 × 4 case is shown below. If the pieces of treasure are buried in the grid sections noted as "#" the two series of numbers become "0,2,2,1,1" and "1,1,1,3".

| 0| 2| 2| 1| 1 ---|---|---|---|---|--- 1| | | #| | 1| | #| | | 1| | | | | # 3| | #| #| #|

Mr. Kobou’s ancestor seems to be a very careful person. He slipped some pieces of paper with completely irrelevant information into the bundle. For example, a set of number series "3,2,3,0,0" and "4,2,0,0,2" does not match any combination of 5 × 5 matrixes. So, Mr. Kobou has first to exclude these pieces of garbage information.

Given the set of information written on the pieces of paper, make a program to judge if the information is relevant.

Input

The input is given in the following format.

$W$ $H$ $a_1$ $a_2$ $...$ $a_W$ $b_1$ $b_2$ $...$ $b_H$

The first line provides the number of horizontal partitions $W$ ($1 \leq W \leq 1000$) and vertical partitions $H$ ($1 \leq H \leq 1000$). The second line provides the $i$-th member of the first number series $a_i$ ($0 \leq a_i \leq H$) written on the paper, and the third line the $j$-th member of the second series $b_j$ ($0 \leq b_j \leq W$).

Output

Output "1" if the information written on the paper is relevant, or "0" otherwise.

Examples

Input

5 4 0 2 2 1 1 1 1 1 3

Output

1

Input

5 5 3 2 3 0 0 4 2 0 0 2

Output

0

inputFormat

Input

The input is given in the following format.

$W$ $H$ $a_1$ $a_2$ $...$ $a_W$ $b_1$ $b_2$ $...$ $b_H$

The first line provides the number of horizontal partitions $W$ ($1 \leq W \leq 1000$) and vertical partitions $H$ ($1 \leq H \leq 1000$). The second line provides the $i$-th member of the first number series $a_i$ ($0 \leq a_i \leq H$) written on the paper, and the third line the $j$-th member of the second series $b_j$ ($0 \leq b_j \leq W$).

outputFormat

Output

Output "1" if the information written on the paper is relevant, or "0" otherwise.

Examples

Input

5 4 0 2 2 1 1 1 1 1 3

Output

1

Input

5 5 3 2 3 0 0 4 2 0 0 2

Output

0

样例

5 5
3 2 3 0 0
4 2 0 0 2

0