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?
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 109.
Input ends with a line containing two zeros.
The output contains only <tt>Yes</tt>' orNo'.
If all processes can be executed, output <tt>Yes</tt>'. Otherwise, outputNo'.
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 0 0
Yes No
Migrated from old NTUJ.
ICPC 2008, Chengdu
| No. | Testdata Range | Score |
|---|