시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB384360.000%

문제

친구들과 즐거운 저녁 식사를 마친 상근이는 각 사람이 돈을 얼마나 내야하는지 계산을 하려고 한다.

이 레스토랑은 카드 결제가 되지 않기 때문에 현금으로 계산해야 한다. 또, 레스토랑은 잔돈을 거슬러주지 않는다.

각 사람이 가지고 있는 현금 정보가 주어졌을 때, 사람들끼리 돈을 적절히 교환해 모든 사람이 정확하게 자기가 내야할 돈을 낼 수 있을까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 식사를 한 사람의 수 N이 주어진다. 다음 N개 줄에는 아래와 같은 정보가 주어진다.

xi ci,1 ci,5 ci,10 ci,25 ci,100 ci,500 ci,1000 ci,2000 ci,5000 ci,10000

xi는 i번 사람이 내야하는 돈을 나타내고, ci,v는 i번 사람이 가지고있는 v원 동전 또는 지폐의 개수이다. 예를 들어, 1번 사람은 1원 동전을 c1,1개, 5원 동전을 c1,5개 가지고 있다.

입력의 마지막 줄에는 0이 하나 주어진다.

모든 사람은 항상 음식값을 낼 수 있으며, 모든 사람이 가지고 있는 돈의 양은 부호있는 32비트 정수 범위 이내이다. 또한, N ≤ 100000이다.

출력

각 테스트 케이스마다 "Case #:"형태로 케이스 번호를 출력하고, 공백을 한 칸 출력한 다음, YES (모든 사람이 돈을 낼 수 있는 경우) 또는 NO (그 외의 경우) 를 출력한다.

예제 입력 1

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
0

예제 출력 1

Case 1: YES
Case 2: YES
Case 3: NO
W3sicHJvYmxlbV9pZCI6Ijc2MTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NGNcdWMyZGRcdWFjMTIiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1YWNmYyBcdWM5OTBcdWFjNzBcdWM2YjQgXHVjODAwXHViMTQxIFx1YzJkZFx1YzBhY1x1Yjk3YyBcdWI5YzhcdWNlNWMgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NzQgXHViM2M4XHVjNzQ0IFx1YzViY1x1YjljOFx1YjA5OCBcdWIwYjRcdWM1N2NcdWQ1NThcdWIyOTRcdWM5YzAgXHVhY2M0XHVjMGIwXHVjNzQ0IFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWI4MDhcdWMyYTRcdWQxYTBcdWI3OTFcdWM3NDAgXHVjZTc0XHViNGRjIFx1YWNiMFx1YzgxY1x1YWMwMCBcdWI0MThcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWQ2MDRcdWFlMDhcdWM3M2NcdWI4NWMgXHVhY2M0XHVjMGIwXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWI4MDhcdWMyYTRcdWQxYTBcdWI3OTFcdWM3NDAgXHVjNzk0XHViM2M4XHVjNzQ0IFx1YWM3MFx1YzJhY1x1YjdlY1x1YzhmY1x1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWQ2MDRcdWFlMDggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1YjA3Y1x1YjlhYyBcdWIzYzhcdWM3NDQgXHVjODAxXHVjODA4XHVkNzg4IFx1YWQ1MFx1ZDY1OFx1ZDU3NCBcdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBcdWM3OTBcdWFlMzBcdWFjMDAgXHViMGI0XHVjNTdjXHVkNTYwIFx1YjNjOFx1Yzc0NCBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyZGRcdWMwYWNcdWI5N2MgXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbng8c3ViPmk8XC9zdWI+IGM8c3ViPmksMTxcL3N1Yj4gYzxzdWI+aSw1PFwvc3ViPiBjPHN1Yj5pLDEwPFwvc3ViPiBjPHN1Yj5pLDI1PFwvc3ViPiBjPHN1Yj5pLDEwMDxcL3N1Yj4gYzxzdWI+aSw1MDA8XC9zdWI+IGM8c3ViPmksMTAwMDxcL3N1Yj4gYzxzdWI+aSwyMDAwPFwvc3ViPiBjPHN1Yj5pLDUwMDA8XC9zdWI+IGM8c3ViPmksMTAwMDA8XC9zdWI+PFwvcHJlPlxyXG5cclxuPHA+eDxzdWI+aTxcL3N1Yj5cdWIyOTQgaVx1YmM4OCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViMGI0XHVjNTdjXHVkNTU4XHViMjk0IFx1YjNjOFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAsIGM8c3ViPmksdjxcL3N1Yj5cdWIyOTQgaVx1YmM4OCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhYzAwXHVjOWMwXHVhY2UwXHVjNzg4XHViMjk0IHZcdWM2ZDAgXHViM2Q5XHVjODA0IFx1YjYxMFx1YjI5NCBcdWM5YzBcdWQzZDBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAxXHViYzg4IFx1YzBhY1x1Yjc4Y1x1Yzc0MCAxXHVjNmQwIFx1YjNkOVx1YzgwNFx1Yzc0NCBjPHN1Yj4xLDE8XC9zdWI+XHVhYzFjLCA1XHVjNmQwIFx1YjNkOVx1YzgwNFx1Yzc0NCBjPHN1Yj4xLDU8XC9zdWI+XHVhYzFjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjNzRjXHVjMmRkXHVhYzEyXHVjNzQ0IFx1YjBiYyBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViM2M4XHVjNzU4IFx1YzU5MVx1Yzc0MCBcdWJkODBcdWQ2MzhcdWM3ODhcdWIyOTQgMzJcdWJlNDRcdWQyYjggXHVjODE1XHVjMjE4IFx1YmM5NFx1YzcwNCBcdWM3NzRcdWIwYjRcdWM3NzRcdWIyZTQuIFx1YjYxMFx1ZDU1YywgTiAmbGU7IDEwMDAwMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCAmcXVvdDtDYXNlICM6JnF1b3Q7XHVkNjE1XHVkMGRjXHViODVjIFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVkNTVjIFx1Y2U3OCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHViMmU0XHVjNzRjLCBZRVMgKFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViM2M4XHVjNzQ0IFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMCkgXHViNjEwXHViMjk0IE5PIChcdWFkZjggXHVjNjc4XHVjNzU4IFx1YWNiZFx1YzZiMCkgXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI3NjE5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmVzdGF1cmFudCB0YWIiLCJkZXNjcmlwdGlvbiI6IjxwPkFmdGVyIGVhdGluZyBkaW5uZXIgYXQgYSByZXN0YXVyYW50IHdpdGggc29tZSBmcmllbmRzLCB5b3UgZGV0ZXJtaW5lIGhvdyBtdWNoIG1vbmV5IGVhY2ggcGVyc29uIG93ZXMuIEVhY2ggb2YgeW91IGhhcyBzb21lIGNhc2ggYW5kIHNvbWUgY2hhbmdlLCBidXQgdmVyeSBmZXcgb2YgeW91IGhhdmUgZXhhY3QgY2hhbmdlLiBDYW4geW91IG1ha2UgY2hhbmdlIGZvciBlYWNoIG90aGVyIHNvIHRoYXQgZWFjaCBwZXJzb24gZW5kcyB1cCBwYXlpbmcgdGhlIGV4YWN0IHJpZ2h0IGFtb3VudD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBcdWZiMDFsZSB3aWxsIGNvbnRhaW4gbXVsdGlwbGUgY2FzZXMuIFRoZSBcdWZiMDFyc3QgbGluZSBvZiBlYWNoIGNhc2UgaXMgTiwgdGhlIG51bWJlciBvZiBwZW9wbGUgYXQgdGhlIHRhYmxlLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IE4gbGluZXMsIG9uZSBmb3IgZWFjaCBpICZpc2luOyBbMSwgTl0sIGNvbnRhaW5pbmc8XC9wPlxyXG5cclxuPHByZT5cclxueDxzdWI+aTxcL3N1Yj4gYzxzdWI+aSwxPFwvc3ViPiBjPHN1Yj5pLDU8XC9zdWI+IGM8c3ViPmksMTA8XC9zdWI+IGM8c3ViPmksMjU8XC9zdWI+IGM8c3ViPmksMTAwPFwvc3ViPiBjPHN1Yj5pLDUwMDxcL3N1Yj4gYzxzdWI+aSwxMDAwPFwvc3ViPiBjPHN1Yj5pLDIwMDA8XC9zdWI+IGM8c3ViPmksNTAwMDxcL3N1Yj4gYzxzdWI+aSwxMDAwMDxcL3N1Yj48XC9wcmU+XHJcblxyXG48cD53aGVyZSB4PHN1Yj5pPFwvc3ViPiBpcyB0aGUgYW1vdW50IGluIGNlbnRzIHRoYXQgcGVyc29uIGkgb3dlcyBhbmQgYzxzdWI+aSx2PFwvc3ViPiBpcyB0aGUgbnVtYmVyIG9mIGNvaW5zIG9yIGJpbGxzIHdvcnRoIHYgY2VudHMgdGhhdCBwZXJzb24gaSBzdGFydHMgb3V0IHdpdGguIEZvciBleGFtcGxlLCBwZXJzb24gMSBoYXMgYzxzdWI+MSwxPFwvc3ViPiBwZW5uaWVzLCBjPHN1Yj4xLDU8XC9zdWI+IG5pY2tlbHMsIGV0Yy48XC9wPlxyXG5cclxuPHA+RWFjaCBjYXNlIGlzIGZvbGxvd2VkIGltbWVkaWF0ZWx5IGJ5IHRoZSBuZXh0IGNhc2UuIFRoZSBlbmQgb2YgdGhlIGlucHV0IGlzIGluZGljYXRlZCBieSBhIGxpbmUgY29udGFpbmluZyBvbmx5IGEgemVyby48XC9wPlxyXG5cclxuPHA+WW91IG1heSBhc3N1bWUgdGhhdCBubyBwZXJzb24gb3dlcyBtb3JlIG1vbmV5IHRoYW4gdGhleSBoYXZlIChpLmUuIHg8c3ViPmk8XC9zdWI+ICZsZTsgJlNpZ21hOzxzdWI+ajxcL3N1Yj5qYzxzdWI+ajxcL3N1Yj4pIGFuZCB0aGF0IHRoZSB0b3RhbCBhbW91bnQgb2YgbW9uZXkgaW4gY2VudHMgdGhhdCBldmVyeW9uZSBzdGFydHMgd2l0aCBcdWZiMDF0cyBpbiBhIHNpZ25lZCAzMi1iaXQgaW50ZWdlci4gWW91IG1heSBhbHNvIGFzc3VtZSB0aGF0IE4gJmxlOyAxMDAwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggY2FzZSwgb3V0cHV0IHRoZSBjYXNlIG51bWJlciwgaW4gdGhlIGZvcm1hdCAmbGRxdW87Q2FzZSAjOiZyZHF1bzsgKHdoZXJlICMgaXMgdGhlIGNhc2UgbnVtYmVyLCBzdGFydGluZyBhdCAxKSwgZm9sbG93ZWQgYnkgYSBzcGFjZSwgZm9sbG93ZWQgYnkgJmxkcXVvO1lFUyZyZHF1bzsgaWYgYWxsIG9mIHRoZSBtb25leSBjYW4gYmUgcmVhcnJhbmdlZCBzbyB0aGF0IGVhY2ggcGVyc29uIGVuZHMgdXAgcGF5aW5nIHRoZSBjb3JyZWN0IGFtb3VudCBhbmQgJmxkcXVvO05PJnJkcXVvOyBpZiBub3QuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==