수정이는 대학교 구내 식당에서 계산원으로 근무하는 직원이다.

모든 학생들은 수정이를 근사하고 멋진 사람으로 생각하는데 그 이유중의 하나는 학생들이 식당을 방문 할 때 가능한 적은 돈으로 식사 할 수 있도록 애써주기 때문이다.

어떻게 그렇게 할까? 방법은 간단하다. 식당에서는 여러 가지 단품음식이 주어지고 각각 가격이 정해져있다. 예를 들면 밥 한공기 이천원, 국 한 대접 천원, 김치 한 접시 천원 등이다.

또한 서로 다른 4개를 하나의 상품으로 묶어 오늘의 메뉴를 제공하는데 그 가격은 각 단품음식의 합보다 작거나 같다고 한다.

어떤 학생이 먹고자 하는 단품음식들을 골라 쟁반에 담아 오면 수정이는 단품음식 가격으로 그 합을 구한 것과 오늘의 메뉴를 고려하여 가능한 적은 가격을 구한 것을 비교하여 더 저렴한 가격으로 계산해준다.

입력 예 1번을 예로 들어보자.

식당에서 제공하는 단품음식의 종류는 7가지 이고 순서대로 1번부터 7번까지 단품음식의 가격은 10, 6, 8, 9, 4, 5, 3 천원이다.

오늘의 메뉴 4가지는 1, 2, 3, 4번 단품음식으로 이루어져 있고 가격은 14 천원이다.

한 학생이 5가지 단품음식을 골랐는데 1, 3, 4, 6, 7이라고 한다.

먼저 단품음식 가격의 합은 10(1번) + 8(3번) + 9(4번) + 5(6번) + 3(7번) = 35 천원이다.

그런데 1, 3, 4가 오늘의 메뉴에 포함된 단품음식이므로 14(1, 3, 4번) + 5(6번) + 3(7번) = 22 천원으로 계산할 수 있다.

이 경우 수정이는 22 천원으로 계산해 준다고 한다.

수정이가 며칠간 휴가를 가고 대신 우석이가 계산원 일을 하게 되었다.

일일이 수동으로 계산하기 귀찮은 우석이는 프로그래머인 당신에게, 이러한 계산을 정확하고 빠르게 할 수 있는 프로그램을 부탁하였다.

우석이를 위하여 프로그램을 작성해 보자.

구내식당(TETA) timer 1초 memory 64MB

구내식당(TETA) 1초 64MB