Snacks within 300 Yen

면접 대비

시간 제한8초메모리 제한1024 MB

요약
과자 가격을 왼쪽부터 차례로 보면서 합계가 300엔을 넘지 않을 때만 장바구니에 담고, 마지막 합계를 출력한다.
난이도

쉬움10점 중 2점

유형
시뮬레이션, 구현, 그리디, 배열
정답자
아직 제출이 없습니다

문제

Your friend, Greedy George, visits a candy store for his snacks for the school excursion, grabbing 300 yen in his hand. In the candy store, one item of each different kind of snack is placed in a line on the shelf. After entering the store, Greedy George picks up a shopping basket and starts checking the snacks on the shelf from left to right. If the sum of the prices of snacks in the basket will not exceed 300 yen, he immediately puts the checked snack into the basket. If the sum should exceed 300 yen, he tearfully skips that snack. After examining all the snacks in this manner to the right end, George heads to the checkout.

Given a list of the prices of the snacks in the store, compute how much money Greedy George will spend.

Figure A-1: The first dataset of Sample Input

입력

The input consists of multiple datasets, each in the following format. The number of datasets does not exceed 50.

n

a1 a2 ⋯ an

n (1 ≤ n ≤ 100) is the number of snacks sold in the candy store. ak (k = 1, …, n) is a positive integer less than or equal to 1000, meaning that the price of the k-th snack from the left is ak yen.

The end of the input is indicated by a line consisting of a zero.

출력

For each dataset, output in a line how many yen Greedy George will spend on the snacks.

예제1

  1. 예제 1

    입력
    5
100 50 200 120 60
4
120 240 180 1
2
500 1000
6
2 3 5 7 11 13
0
    예상 출력
    270
300
0
41