Paying the Dinner Bill

You and your friends have just finished a pleasant dinner, and now everyone has to pay their share.

The restaurant does not accept cards, so the bill must be paid in cash, and it gives no change. Therefore each person must pay their share exactly.

The people who shared the dinner may freely exchange coins and bills with one another to gather the amounts they need. Because money can be exchanged freely like this, what really matters is whether, by pooling everyone's cash, the group can pay the total of all shares exactly, without needing a single unit of change.

Given the cash each person starts with, decide whether the group can pay the exact total of everyone's shares.

The input consists of several test cases.

The first line of each test case contains the number of people $N$. Each of the next $N$ lines describes one person in the following order:

x c1 c5 c10 c25 c100 c500 c1000 c2000 c5000 c10000

Here $x$ is the amount that person must pay, and $c_v$ is the number of coins or bills of denomination $v$ that person holds. The ten denominations are $1, 5, 10, 25, 100, 500, 1000, 2000, 5000, 10000$.

The last line of the input contains a single $0$, marking the end of the input.

Every person always holds at least as much cash as the amount they must pay, and the total cash held by each person fits in a signed 32-bit integer. Also, $N \le 100000$.

For each test case, print Case k: (where $k$ is the case number starting from 1), a single space, and then YES if everyone can pay exactly, or NO otherwise.