Informatica Online Judge

  GSHS 카페 [1300 / 0514]

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


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (32nd 이선호)]

Background

GSHS에 새로 만들어진 동아리실에는 경곽 학생들의 심리적 안정과 부가적 간식 제공을 목적으로 "경곽Cafe"라는 이름의 카페가 설립되었다.

바리스타 동아리를 통해 운영되는 “경곽Cafe"에서는 설문지 조사를 통해 1번.아메리카노, 2번.카페라테, 3번.카푸치노, 4번.카라멜마끼아또,

5번.카페모카, 6번.에스프레소 총 6가지 커피를 팔기로 하였다.

그런데, 이 바리스타의 기장 철순이는 너무나도 괴팍하고 변덕쟁이여서 사람들이 주문할 때마다 커피가격을 바꾼다.


어느날, 경곽이를 포함한 (m+1)명의 학생들이 SRC에서 알앤이를 진행하던 도중에 카페인이 필요함을 느끼고 가위바위보 내기를 하여 진 사람이 나머지 m명의 커피를 진 사람의 돈으로 사오기로 하였다.

안타깝게도, 경곽이가 그 내기에서 지게 되어서 m개의 커피를 사오게 되었다.

철순이의 영업철학을 잘 알고 있는 경곽이는 최소한의 금액을 가지고 m개의 커피를 사고 싶다.

경곽이를 위해 최소 금액을 구해보자!!


(여기서, SRC에서 카페까지의 길은 멀고 험난하여 한번에 하나씩 사올 수 있어 m개의 커피를 사오려면 m번 왕복해야 한다.)

Input

첫째 줄에 정수 m이 주어진다. 이는 경곽이가 사야할 커피의 수이다.

둘째 줄에 P1~P6 이 입력된다. Pi는 경곽이가 사야할 I번째 커피의 개수이다. P1 ~ P6의 합은 m이다.

그로부터 m개의 줄에 가격표 X1~X6이 입력된다. 각 줄의 Xi는 각 왕복마다 I번째 커피를 사는데 필요한 금액이다.

(계속 왕복할 때 마다 철순이가 금액을 바꾸기 때문에 m개의 가격표가 주어진다.)

[입력값의 정의역]
1 <= m <= 50
1 <= Pi <= 9

Output

경곽이가 m개의 커피를 모두 사는 데에 필요한 최소한의 비용을 출력한다.

IO Example

입력
9
3 1 2 1 0 2
6 1 11 5 9 2
11 4 3 5 4 3
10 5 4 8 10 1
1 9 7 3 4 1
5 2 6 4 11 1
10 6 12 6 5 4
1 12 12 3 12 1
2 11 11 9 3 1
3 9 2 1 1 5

출력
18

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