Informatica Online Judge

  숫자 페인팅 [0868 / 0364]

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


The Champion of this Problem (C++) : gs16051 - ms / 269byte
My Best Submission (C++) : N/A

[]

Background

경곽이는 이번에 학교 벽에 큰 숫자를 쓰기로 했다.

숫자는 $1$부터 $9$까지의 $9$개로 구성되고 각 숫자들을 쓰는데 필요한 페인트 량은 정해져 있다.

경곽이는 현재 페인트를 $d$리터를 가지고 있으며, 각 숫자들을 쓰는데 사용하는 페인트 량을 알고 있다고 할 때,

경곽이가 벽에 쓸 수 있는 가장 큰 수가 얼마인지 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 페인트의 양을 나타내는 값 $d$가 입력된다.

두 번째 줄에 $1$부터 $9$까지 각 숫자들을 쓰는데 사용하는 페인트 량 $x_i$가 공백으로 구분되어 입력된다.

[입력값의 정의역]
$0≤d≤1,000,000$
$1≤x_i≤100,000$

Output

벽에 쓸 수 있는 가장 큰 수를 출력한다.

IO Example

입력
5
5 4 3 2 1 2 3 4 5

출력
55555

* 1, 2, 3, ... ,9를 쓰는데 각각 5 4 3 2 1 2 3 4 5리터가 든다. 따라서 총 5리터를 이용하여 쓸 수 있는 가장 큰 수는 1리터로 한자를 쓸 수 있는 5를 5번 쓴 55555가 가장 큰 수이고 더 큰 수를 쓸 수 있는 방법은 없다.

입력2
2
9 11 1 12 5 8 9 10 6

출력2
33

입력3
0
1 1 1 1 1 1 1 1 1

출력3
-1

* 이 경우는 수를 적을 수 없으므로 -1을 출력한다.

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