1195 - 宝の地図

時間制限 1 秒 / メモリ制限 256 MB / 得点 8 / Writer root / x 2 / 統計 /


TLE
1sec
MLE
256MB
得点
8

実家の蔵を掃除していたコボウ氏は、古い紙の束を見つけた。それぞれの紙には2つの数列が書いてある。不思議に思ったコボウ氏が蔵の中を探すと、先祖が残したメモが見つかった。それによると、この紙は先祖が残した宝の地図で、2つの数列は宝が埋まっている場所の手がかりを表しているらしい。

紙に書かれた数列は、ある場所を格子状に区切ってできる区画のそれぞれの列と行に、いくつ宝が埋まっているかを表している。1つ目の数列の $i$ 番目の数は、左から $i$ 番目の列にいくつ宝が埋まっているかを表している。同様に、2つ目の数列の$j$ 番目の数は、上から $j$ 番目の行にいくつ宝が埋まっているかを表している。1つの区画内に埋まっている宝は高々1つである。たとえば、横方向に5つと縦方向に4つ並んだ区画のうち、下の図の#で示した区画に宝が埋まっているときは、0,2,2,1,1 と 1,1,1,3 という数列で表される。

02211
1 #
1 #
1 #
3 ###

用心深い先祖は、紙に書かれた数列の意味を推測しにくくするために、有り得ない情報が書かれた紙を紛れ込ませていた。たとえば 3,2,3,0,0 と 4,2,0,0,2 という数列は、横方向と縦方向に5つずつ並んだ区画に宝が埋まっているどのような状況にもあてはまらない。コボウ氏が宝を見つけるには、有り得ない情報が書かれている紙を除外しなければならない。

紙に書かれた情報が与えられたとき、紙に書かれた情報が有り得るかどうかを判定するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

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

1行目に、紙に書かれた横方向の区画の数$W$ ($1 \leq W \leq 1000$)と縦方向の区画の数$H$ ($1 \leq H \leq 1000$)が与えられる。2行目に、その紙に書かれた1つ目の数列の$i$番目の数$a_i$ ($0 \leq a_i \leq H$)が与えられる。3行目に、その紙に書かれた2つ目の数列の$j$番目の数$b_j$ ($0 \leq b_j \leq W$)が与えられる。

出力

紙に書かれている情報が有り得るなら「1」を、有り得ないなら「0」を1行に出力する。

入出力例

入力例1

5 4
0 2 2 1 1
1 1 1 3

出力例1

1

入力例2

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

出力例2

0