Informatica Online Judge

  치킨 볼 [1165 / 048D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 17   Total Tried : 19


The Champion of this Problem (C++) : gs14092 - 0ms / 227byte
My Best Submission (C++) : N/A

[USACO]

Background

경곽이는 아르바이트를 하기 위해 치킨 볼 집에 취직했다.

이 치킨 볼 집은 날마다 n가지의 치킨볼 패키지를 판매한다.

각 패키지는 서로 다른 수의 치킨 볼이 들어 있다.

패키지에는 1개~256개까지의 치킨 볼을 적절히 설정한다.

만약 어느날 패키지의 종류가 3가지이고, 각 패키지의 치킨 볼의 수가 각각 3, 6, 10이라고 하자.

어떤 손님이 치킨볼 18개를 사려면 6, 6, 6세트로 판매할 수 있고, 9개를 사려면 3, 6으로 판매할 수 있다.

하지만 2개를 사거나 17개를 사려고 하면 어떻게 해서도 판매할 수 없다.

어느 날의 치킨 볼의 세트 종류의 수와 각 치킨 볼의 개수가 주어질 때, 판매할 수 없는 치킨 볼의 수의 최댓값을 출력하시오.

Input

첫 번째 줄에 세트의 종류의 수 n이 입력된다.

두 번째 줄에 n개의 세트에 들어있는 치킨볼의 수가 입력된다.

단 n은 10이하의 자연수이다.

Output

판매할 수 없는 최대 치킨 볼의 수를 출력한다.

만약 모든 수가 가능하거나, 팔 수 없는 수가 무한하다면 0을 출력한다.

IO Example

입력
3
3 6 10

출력
17

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]