Submit | All submissions | Best solutions | Back to list |

## RSTAURNT - Restaurant Tab |

After eating dinner at a restaurant with some friends, you determine how much money each person owes. Each of you has some cash and some change, but very few of you have exact change. Can you make change for each other so that each person ends up paying the exact right amount?

### Input

The input file will contain multiple cases. The first line of each
case is N, the number of people at the table. This is followed
by N lines, one for each i ∈ [1,N], containing

x_{i} | c_{i,1} | c_{i,5} | c_{i,10} | c_{i,25} | c_{i,100} | c_{i,500} | c_{i,1000} | c_{i,2000} | c_{i,5000} | c_{i,10000} |

where x_{i} is the amount in cents that person i owes and c_{i,v}
is the number of coins or bills worth v cents that person i
starts out with. For example, person 1 has c_{1,1} pennies, c_{1,5}
nickels, etc.
Each case is followed immediately by the next case. The end of the
input is indicated by a line containing only a zero.
You may assume that no person owes more money than they have (i.e.
x_{i} ≤ Σ_{j} j*c_{i,j}) and that the total amount of money in cents that
everyone starts with fits in a signed 32-bit integer. You may also
assume that N ≤ 100000.

### Output

For each case, output the case number, in the format "Case #:" (where # is the case number, starting at 1), followed by a space, followed by "YES" if all of the money can be rearranged so that each person ends up paying the correct amount and "NO" if not.

### Example

Input:1 10 0 0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 500 0 0 0 0 0 1 0 0 0 0 1 100 4 0 2 3 0 1 0 0 0 0 0Output:Case 1: YES Case 2: YES Case 3: NO

Added by: | Minilek |

Date: | 2008-12-22 |

Time limit: | 5.986s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP clisp LISP sbcl D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |

Resource: | MIT Individual Contest 2008 |