Snacks within 300 Yen

Interview

Time limit8sMemory limit1024 MB

Summary

Greedy George walks a shelf of snack prices left to right and buys each snack that keeps his total within 300 yen. The task is to output his total spending for each dataset.

Level: Easy2 of 10
Topics: Greedy, Simulation
Solved: No attempts yet

Problem

Your friend, Greedy George, visits a candy store to buy snacks for a school excursion. He holds 300 yen in his hand. The candy store places one item of each kind of snack in a line on the shelf. After entering the store, George picks up a shopping basket and checks the snacks on the shelf from left to right. If the sum of the prices of the snacks in the basket does not exceed 300 yen, he puts the checked snack into the basket right away. If the sum would exceed 300 yen, he tearfully skips that snack. After checking every snack up to the right end, George goes to the checkout.

Given the list of snack prices in the store, compute how much money Greedy George spends.

Figure A-1: The first dataset of the sample input

Input

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

$n$

$a_1$ $a_2$ $\cdots$ $a_n$

$n$ ( $1 \le n \le 100$ ) is the number of snacks sold in the candy store. $a_k$ ( $k = 1, \ldots, n$ ) is a positive integer at most 1000, meaning that the price of the $k$ -th snack from the left is $a_k$ yen.

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

Output

For each dataset, output on one line how many yen Greedy George spends on snacks.

Examples1

Example 1

Input

5
100 50 200 120 60
4
120 240 180 1
2
500 1000
6
2 3 5 7 11 13
0

Expected output