Problem: 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

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


//Dinic

#define NUM 2005


//辺を表す構造体(行先、容量、逆辺のインデックス)
struct Edge{
	Edge(int arg_to,int arg_capacity,int arg_rev_index){
		to = arg_to;
		capacity = arg_capacity;
		rev_index = arg_rev_index;
	}
	int to,capacity,rev_index;
};

int V;
int index_row[NUM],index_col[NUM];

vector<Edge> G[NUM]; //グラフの隣接リスト表現
int dist[NUM]; //sourceからの距離
int cheked_index[NUM]; //どこまで調べ終わったか

//fromからtoへ向かう容量capacityの辺をグラフに追加する
void add_edge(int from,int to,int capacity){
	G[from].push_back(Edge(to,capacity,G[to].size()));
	G[to].push_back(Edge(from,0,G[from].size()-1)); //逆辺の、初期容量は0
}

//sourceからの最短距離をBFSで計算する
void bfs(int source){
	for(int i = 0; i < V; i++)dist[i] = -1;
	queue<int> Q;
	dist[source] = 0;
	Q.push(source);

	while(!Q.empty()){
		int node_id = Q.front();
		Q.pop();
		for(int i = 0; i < G[node_id].size(); i++){
			Edge &e = G[node_id][i];
			if(e.capacity > 0 && dist[e.to] < 0){ //辺の容量が正で、かつエッジの行先に未訪問の場合
				dist[e.to] = dist[node_id]+1;
				Q.push(e.to);
			}
		}
	}
}

//増加パスをDFSで探す
int dfs(int node_id,int sink,int flow){
	if(node_id == sink)return flow; //終点についたらflowをreturn

	for(int &i = cheked_index[node_id]; i < G[node_id].size(); i++){ //node_idから出ているエッジを調査
		Edge &e = G[node_id][i];
		if(e.capacity > 0 && dist[node_id] < dist[e.to]){ //流せる余裕があり、かつsourceからの距離が増加する方法である場合
			int tmp_flow = dfs(e.to,sink,min(flow,e.capacity)); //流せるだけ流す
			if(tmp_flow > 0){ //流せた場合
				e.capacity -= tmp_flow; //流した分、エッジの容量を削減する
				G[e.to][e.rev_index].capacity += tmp_flow; //逆辺の容量を、流した分だけ増加させる
				return tmp_flow;
			}
		}
	}
	return 0;
}


//sourceからsinkへの最大流を求める
int max_flow(int source,int sink){ //source:始点 sink:終点
	int flow = 0,add;
	while(true){ //増加パスが存在する限り、流量を追加し続ける
		bfs(source);
		if(dist[sink] < 0)break; //sourceからsinkへと辿り着く残余グラフがない、つまり増加パスが無くなった場合、break
		for(int i = 0; i < V; i++)cheked_index[i] = 0;
		while((add = dfs(source,sink,BIG_NUM)) > 0){ //増加パスが見つかる間、加算
			flow += add;
		}
	}
	return flow;
}


int main(){

	int num_row,num_col;

	scanf("%d %d",&num_row,&num_col);

	int source = 0,sink = 1;
	int index = 2;
	//採番
	for(int i = 0; i < num_row; i++){

		index_row[i] = index++;
	}
	for(int i = 0; i < num_col; i++){

		index_col[i] = index++;
	}

	int capacity;
	int row_sum = 0,col_sum = 0;

	//行の情報
	for(int i = 0; i < num_row; i++){

		scanf("%d",&capacity);
		add_edge(source,index_row[i],capacity);
		row_sum += capacity;
	}
	//列の情報
	for(int i = 0; i < num_col; i++){

		scanf("%d",&capacity);
		add_edge(index_col[i],sink,capacity);
		col_sum += capacity;
	}

	if(row_sum != col_sum){

		printf("0\n");
		return 0;
	}

	//行と列を1対1に対応づける
	for(int i = 0; i < num_row; i++){
		for(int k = 0; k < num_col; k++){
			add_edge(index_row[i],index_col[k],1);
		}
	}

	V = index;
	//最大流で行と列をマッチング
	if(row_sum == max_flow(source,sink)){

		printf("1\n");

	}else{

		printf("0\n");
	}

	return 0;
}