시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB230529507825541.593%

문제

슈퍼 마리오 앞에 10개의 버섯이 일렬로 놓여져 있다. 이 버섯을 먹으면 점수를 받는다.

슈퍼 마리오는 버섯을 처음부터 나온 순서대로 집으려고 한다. 하지만, 모든 버섯을 집을 필요는 없고 중간에 중단할 수 있다. 중간에 버섯을 먹는 것을 중단했다면, 그 이후에 나온 버섯은 모두 먹을 수 없다. 따라서 첫 버섯을 먹지 않았다면, 그 이후 버섯도 모두 먹을 수 없다.

마리오는 받은 점수의 합을 최대한 100에 가깝게 만들려고 한다.

버섯의 점수가 주어졌을 때, 마리오가 받는 점수를 출력하는 프로그램을 작성하시오.

입력

총 10개의 줄에 각각의 버섯의 점수가 주어진다. 이 값은 100보다 작거나 같은 양의 정수이다. 버섯이 나온 순서대로 점수가 주어진다.

출력

첫째 줄에 마리오가 받는 점수를 출력한다. 만약 100에 가까운 수가 2개라면 (예: 98, 102) 마리오는 큰 값을 선택한다.

예제 입력 1

10
20
30
40
50
60
70
80
90
100

예제 출력 1

100

예제 입력 2

1
2
3
5
8
13
21
34
55
89

예제 출력 2

87

예제 입력 3

40
40
40
40
40
40
40
40
40
40

예제 출력 3

120
W3sicHJvYmxlbV9pZCI6IjI4NTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyODhcdWQzN2MgXHViOWM4XHViOWFjXHVjNjI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyODhcdWQzN2MgXHViOWM4XHViOWFjXHVjNjI0IFx1YzU1ZVx1YzVkMCAxMFx1YWMxY1x1Yzc1OCBcdWJjODRcdWMxMmZcdWM3NzQgXHVjNzdjXHViODJjXHViODVjIFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJjODRcdWMxMmZcdWM3NDQgXHViYTM5XHVjNzNjXHViYTc0IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWJjMWJcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzI4OFx1ZDM3YyBcdWI5YzhcdWI5YWNcdWM2MjRcdWIyOTQgXHViYzg0XHVjMTJmXHVjNzQ0IFx1Y2M5OFx1Yzc0Y1x1YmQ4MFx1ZDEzMCBcdWIwOThcdWM2MjggXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzlkMVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHViYWE4XHViNGUwIFx1YmM4NFx1YzEyZlx1Yzc0NCBcdWM5ZDFcdWM3NDQgXHVkNTQ0XHVjNjk0XHViMjk0IFx1YzVjNlx1YWNlMCBcdWM5MTFcdWFjMDRcdWM1ZDAgXHVjOTExXHViMmU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzkxMVx1YWMwNFx1YzVkMCBcdWJjODRcdWMxMmZcdWM3NDQgXHViYTM5XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM5MTFcdWIyZThcdWQ1ODhcdWIyZTRcdWJhNzQsIFx1YWRmOCBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHViMDk4XHVjNjI4IFx1YmM4NFx1YzEyZlx1Yzc0MCBcdWJhYThcdWI0NTAgXHViYTM5XHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWNjYWIgXHViYzg0XHVjMTJmXHVjNzQ0IFx1YmEzOVx1YzljMCBcdWM1NGFcdWM1NThcdWIyZTRcdWJhNzQsIFx1YWRmOCBcdWM3NzRcdWQ2YzQgXHViYzg0XHVjMTJmXHViM2M0IFx1YmFhOFx1YjQ1MCBcdWJhMzlcdWM3NDQgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHViOWFjXHVjNjI0XHViMjk0IFx1YmMxYlx1Yzc0MCBcdWM4MTBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyAxMDBcdWM1ZDAgXHVhYzAwXHVhZTVkXHVhYzhjIFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmM4NFx1YzEyZlx1Yzc1OCBcdWM4MTBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViOWM4XHViOWFjXHVjNjI0XHVhYzAwIFx1YmMxYlx1YjI5NCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNkMWQgMTBcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJjODRcdWMxMmZcdWM3NTggXHVjODEwXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0MCAxMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWJjODRcdWMxMmZcdWM3NzQgXHViMDk4XHVjNjI4IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4MTBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViOWM4XHViOWFjXHVjNjI0XHVhYzAwIFx1YmMxYlx1YjI5NCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgMTAwXHVjNWQwIFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWMyMThcdWFjMDAgMlx1YWMxY1x1Yjc3Y1x1YmE3NCAoXHVjNjA4OiA5OCwgMTAyKSBcdWI5YzhcdWI5YWNcdWM2MjRcdWIyOTQgXHVkMDcwIFx1YWMxMlx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjg1MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdMSklWRSIsImRlc2NyaXB0aW9uIjoiPHA+SW4gZnJvbnQgb2YgU3VwZXIgTWFyaW8gdGhlcmUgYXJlIDEwIG11c2hyb29tcywgYXJyYW5nZWQgaW4gYSByb3cuIEEgY2VydGFpbiBhbW91bnQgb2YgcG9pbnRzIGlzIGF3YXJkZWQgZm9yIHBpY2tpbmcgZWFjaCBvZiB0aGUgbXVzaHJvb21zLiBTdXBlciBNYXJpbyBtdXN0IHBpY2sgbXVzaHJvb21zIGluIG9yZGVyIHRoZXkgYXBwZWFyLCBidXQgaXMgbm90IHJlcXVpcmVkIHRvIHBpY2sgdGhlbSBhbGwgJm5kYXNoOyBoaXMgZ29hbCBpcyB0byBzY29yZSBhIG51bWJlciBvZiBwb2ludHMgYXMgY2xvc2UgYXMgcG9zc2libGUgdG8gMTAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiBjYXNlIHRoZXJlIGV4aXN0IHR3byBzdWNoIG51bWJlcnMgd2hpY2ggYXJlIGVxdWFsbHkgY2xvc2UgdG8gMTAwIChlLmcuIDk4IGFuZCAxMDIpLCBNYXJpbyB3aWxsIHBpY2sgdGhlIGdyZWF0ZXIgb25lIChpbiB0aGlzIGNhc2UgMTAyKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SGVscCBTdXBlciBNYXJpbyBhbmQgdGVsbCBoaW0gaG93IG1hbnkgcG9pbnRzIGhlIHdpbGwgc2NvcmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBjb25zaXN0cyBvZiAxMCBsaW5lcywgZWFjaCBvZiB3aGljaCBjb250YWlucyBvbmUgcG9zaXRpdmUgaW50ZWdlciBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMTAwLCBkZW5vdGluZyB0aGUgc2NvcmVzIGF3YXJkZWQgZm9yIHBpY2tpbmcgZWFjaCBtdXNocm9vbSwgaW4gdGhlIG9yZGVyIHRoYXQgTWFyaW8gY2FuIHBpY2sgdGhlbSBpbi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBudW1iZXIgb2YgcG9pbnRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #5 1번