Process scheduling

Time Limit: 5000/2000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

Process scheduling is a very important problem in operating system design. Each process requires some amount of resources to run. The process will release all the resources allocated to it when completes. Different resource allocating strategy varies much in efficiency. Even some unsuitable strategy can result in dead lock.
Now there are n processes and m kinds of resources. At the beginning, each process has been allocated some amount of resources for each kind. However, the allocated resources might not be enough. They still need some extra resources for each kind. And you are given the available resources for each kind in the computer now. Can you tell whether it is possible to schedule these processes in a suitable order so that all of them can be executed successfully?

Input

There are four parts in the input.
The first part contains two positive integers n(n<=50000) and m(m<=3) representing the number of processes and the number of resources.
The second part is the following m lines. Each of the m lines contains n integers. These integers make the allocation table.
The third part is also the following m lines. Each of the m lines contains n integers. These integers make the request table.
The last line containing m integers is the fourth part. This part tells you the amount of available resources for each kind currently.
You may assume all integers that appear are less than or equal to 10^9.

Output

The output contains only ‘Yes’ or ‘No’.
If all processes can be executed, output ‘Yes’. Otherwise, output ‘No’.

Sample Input

4 3 1 6 2 0 0 1 1 0 0 2 1 2 2 0 1 4 2 0 0 2 2 1 3 0 0 1 1 4 3 2 5 2 0 0 1 1 0 1 1 1 2 1 1 1 4 2 0 0 2 1 2 3 0 0 1 1

Sample Output

Yes No

Hint

lcy

Source

2008 Asia Regional Chengdu

提交代码