In xCPC contest, there are totally types of problems. Now you have problems in type , and you want to make some problemsets with these problems.

In your opinion, the number of problems in one problemset must be in interval , and the number of problems in type must be in interval .

Now you want to know the maximum number of problemsets you can make, where one problem can be used in no more than one problemset.

The first line contains three integers .

The second line contains  integers .

Following  lines each contains two integers .

Only one line containing one integer, denoting the maximum number of problemsets you can make.

4 10 12
4 20 10 6
1 2
3 5
2 4
0 2

4

One possible scheme is .