There was an issue with problem I (Omar's Gifts) that gave a WA verdict to correct solutions. The solutions have been rejudged now, so check if your solution is now accepted before resubmitting.
Omar is in the UAE and he wants to buy a present for each of his $N$ friends. Each present can be bought from $M$ different online stores, e.g. Noon, Opensooq, Amazon, etc. The $i^{{th}}$ friend wants the $i^{{th}}$ present and it has integer price $A_{ij}$ in the $j^{{th}}$ store. If the present is out of stock $A_{ij}$ would be $-1$.
If any of his friends don't receive a gift they will be very sad. Omar has only $K$ AED (United Arab Emirates Dirham), is it possible to buy all his $N$ friends gifts in a way where nobody gets sad? If it's possible print YES otherwise print NO.
The first line of input contains three integers: $N$, $M$, and $K$ ($1$ $\leq$ $N$,$M$ $\leq$ $500$, $1$ $\leq$ $K$ $\leq$ $10^{9}$) --- the number of Omar's friends, the number of online stores, and the amount of money Omar has, respectively.
Each of the following $N$ lines contains $M$ space-separated integers $A_{i1}$, $A_{i2}$, ..., $A_{iM}$ ($-1$ $\leq$ $A_{ij}$ $\leq$ $100$), where $A_{ij}$ is the price of the $i^{{th}}$ gift in the $j^{{th}}$ store.
If it is impossible for Omar to buy gifts for all his friends, print NO. Otherwise, print YES.
| Input | Output |
|---|---|
2 3 20 30 19 20 1 19 -1 Copy
|
YES Copy
|
2 2 100000 1 100 -1 -1 Copy
|
NO Copy
|
2 3 10 10 20 30 1 1 1 Copy
|
NO Copy
|