시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 6759 3884 3314 61.898%

문제

선영이의 집에는 콘센트를 꽂을 수 있는 플러그가 하나밖에 없다. 선영이는 많은 컴퓨터를 가지고 있는데, 컴퓨터의 전원 문제는 어떻게 해결하는 것일까?

하나의 플러그가 있고, N개의 멀티탭이 있다. 각 멀티탭은 몇 개의 플러그로 이루어져 있다고 한다. 최대 몇 대의 컴퓨터를 전원에 연결할 수 있을까?

입력

첫째 줄에 멀티탭의 개수 N이 주어진다. (1<=N<=500,000) 이어서 둘째 줄부터 N개의 줄에 걸쳐 각 멀티탭이 몇 개의 플러그를 꽂을 수 있도록 되어 있는지를 나타내는 자연수가 주어진다. 이 자연수는 1,000을 넘지 않는다.

출력

첫째 줄에 최대로 전원에 연결될 수 있는 컴퓨터의 수를 출력한다.

예제 입력 1

3
1
1
1

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjIwMTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1MGNcdWI3ZWNcdWFkZjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1Yzc1OCBcdWM5ZDFcdWM1ZDBcdWIyOTQgXHVjZjU4XHVjMTNjXHVkMmI4XHViOTdjIFx1YWY0Mlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDUwY1x1YjdlY1x1YWRmOFx1YWMwMCBcdWQ1NThcdWIwOThcdWJjMTZcdWM1ZDAgXHVjNWM2XHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViOWNlXHVjNzQwIFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0XHViMzcwLCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWM3NTggXHVjODA0XHVjNmQwIFx1YmIzOFx1YzgxY1x1YjI5NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVkNTc0XHVhY2IwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3Y1x1YWU0Yz88XC9wPlxyXG5cclxuPHA+XHVkNTU4XHViMDk4XHVjNzU4IFx1ZDUwY1x1YjdlY1x1YWRmOFx1YWMwMCBcdWM3ODhcdWFjZTAsIE5cdWFjMWNcdWM3NTggXHViYTQwXHVkMmYwXHVkMGVkXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YmE0MFx1ZDJmMFx1ZDBlZFx1Yzc0MCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1ZDUwY1x1YjdlY1x1YWRmOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjZDVjXHViMzAwIFx1YmE4NyBcdWIzMDBcdWM3NTggXHVjZWY0XHVkNGU4XHVkMTMwXHViOTdjIFx1YzgwNFx1YzZkMFx1YzVkMCBcdWM1ZjBcdWFjYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYTQwXHVkMmYwXHVkMGVkXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEmbHQ7PU4mbHQ7PTUwMCwwMDApIFx1Yzc3NFx1YzViNFx1YzExYyBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWFjMDEgXHViYTQwXHVkMmYwXHVkMGVkXHVjNzc0IFx1YmE4NyBcdWFjMWNcdWM3NTggXHVkNTBjXHViN2VjXHVhZGY4XHViOTdjIFx1YWY0Mlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTRcdWM5YzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM3OTBcdWM1ZjBcdWMyMThcdWIyOTQgMSwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWM4MDRcdWM2ZDBcdWM1ZDAgXHVjNWYwXHVhY2IwXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZWY0XHVkNGU4XHVkMTMwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjAxMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVsZWN0cmljYWwgT3V0bGV0cyIsImRlc2NyaXB0aW9uIjoiPHA+Um95IGhhcyBqdXN0IG1vdmVkIGludG8gYSBuZXcgYXBhcnRtZW50LiBXZWxsLCBhY3R1YWxseSB0aGUgYXBhcnRtZW50IGl0c2VsZiBpcyBub3QgdmVyeSBuZXcsIGV2ZW4gZGF0aW5nIGJhY2sgdG8gdGhlIGRheXMgYmVmb3JlIHBlb3BsZSBoYWQgZWxlY3RyaWNpdHkgaW4gdGhlaXIgaG91c2VzLiBCZWNhdXNlIG9mIHRoaXMsIFJveSZyc3F1bztzIGFwYXJ0bWVudCBoYXMgb25seSBvbmUgc2luZ2xlIHdhbGwgb3V0bGV0LCBzbyBSb3kgY2FuIG9ubHkgcG93ZXIgb25lIG9mIGhpcyBlbGVjdHJpY2FsIGFwcGxpYW5jZXMgYXQgYSB0aW1lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Sb3kgbGlrZXMgdG8gd2F0Y2ggVFYgYXMgaGUgd29ya3Mgb24gaGlzIGNvbXB1dGVyLCBhbmQgdG8gbGlzdGVuIHRvIGhpcyBIaUZpIHN5c3RlbSAob24gaGlnaCB2b2x1bWUpIHdoaWxlIGhlIHZhY3V1bXMsIHNvIHVzaW5nIGp1c3QgdGhlIHNpbmdsZSBvdXRsZXQgaXMgbm90IGFuIG9wdGlvbi4gQWN0dWFsbHksIGhlIHdhbnRzIHRvIGhhdmUgYWxsIGhpcyBhcHBsaWFuY2VzIGNvbm5lY3RlZCB0byBhIHBvd2VyZWQgb3V0bGV0LCBhbGwgdGhlIHRpbWUuIFRoZSBhbnN3ZXIsIG9mIGNvdXJzZSwgaXMgcG93ZXIgc3RyaXBzLCBhbmQgUm95IGhhcyBzb21lIG9sZCBvbmVzIHRoYXQgaGUgdXNlZCBpbiBoaXMgb2xkIGFwYXJ0bWVudC4gSG93ZXZlciwgdGhhdCBhcGFydG1lbnQgaGFkIG1hbnkgbW9yZSB3YWxsIG91dGxldHMsIHNvIGhlIGlzIG5vdCBzdXJlIHdoZXRoZXIgaGlzIHBvd2VyIHN0cmlwcyB3aWxsIHByb3ZpZGUgaGltIHdpdGggZW5vdWdoIG91dGxldHMgbm93LjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gaGVscCBSb3kgY29tcHV0ZSBob3cgbWFueSBhcHBsaWFuY2VzIGhlIGNhbiBwcm92aWRlIHdpdGggZWxlY3RyaWNpdHksIGdpdmVuIGEgc2V0IG9mIHBvd2VyIHN0cmlwcy4gTm90ZSB0aGF0IHdpdGhvdXQgYW55IHBvd2VyIHN0cmlwcywgUm95IGNhbiBwb3dlciBvbmUgc2luZ2xlIGFwcGxpYW5jZSB0aHJvdWdoIHRoZSB3YWxsIG91dGxldC4gQWxzbywgcmVtZW1iZXIgdGhhdCBhIHBvd2VyIHN0cmlwIGhhcyB0byBiZSBwb3dlcmVkIGl0c2VsZiB0byBiZSBvZiBhbnkgdXNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQmbmJzcDtzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIDEgJmxlOyBLICZsZTsgMTAsIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiBwb3dlciBzdHJpcHMgaW4gdGhlIHRlc3QgY2FzZS4gVGhlbiBmb2xsb3csIG9uIHRoZSBzYW1lIGxpbmUsIEsgaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMsIE8xIE8yIC4gLiAuIE9LLCB3aGVyZSAyICZsZTsgT2kgJmxlOyAxMCwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIG91dGxldHMgaW4gZWFjaCBwb3dlciBzdHJpcC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGxpbmUsJm5ic3A7dGhlIG1heGltdW0gbnVtYmVyIG9mIGFwcGxpYW5jZXMgdGhhdCBjYW4gYmUgcG93ZXJlZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=