그리디한 인심

많은 통화는 액면마다 동전이 충분히 있을 때 그리디 방식으로 거스름돈을 만들면 동전 개수가 최소가 되도록 설계되어 있다. 그리디 방식은 남은 금액을 넘지 않는 가장 큰 액면의 동전을 반복해서 고른다. 이 문제의 통화에는 1센트, 2센트, 5센트, 10센트, 20센트, 50센트 동전이 있다. 77센트를 거슬러 준다면 그리디 방식은 50센트, 20센트, 5센트, 2센트를 차례로 고른다.

요즘 몇몇 가게는 손님이 돈을 넣으면 필요한 거스름돈을 내어 주는 무인 계산대를 들여놓았다. 가게는 손님이 이 기계를 쓰도록 유도하고 싶어 한다. 넣은 돈보다 적게 돌려주기 쉬운 도박 기계에서 아이디어를 빌려, 가게가 쓸 만한 방법을 하나 생각해 보자.

무인 계산대는 액면마다 동전을 일정량 갖고 있고, 하루를 기준 재고에서 시작한다. 기계는 항상 앞에서 설명한 그리디 방식으로 거스름돈을 준다. 남은 금액을 넘지 않는 가장 큰 액면의 동전이 재고에 없으면 기계는 더 작은 동전으로 대신하지 않고, 대신 손님에게 인심을 쓴다.

인심을 쓰는 방식은 이렇다. 그리디 방식으로 동전을 낼 수 없으면, 그리디 방식으로 낼 수 있게 되는 최소한의 금액까지 거스름돈을 올린다. 5센트 동전 두 개와 20센트 동전 한 개가 있고 10센트 동전은 하나도 없는 기계가 10센트를 거슬러 주어야 한다면, 기계는 20센트 동전을 준다. 이런 지급이 일어나면 도박 기계처럼 부저가 울리고 조명이 번쩍이며, 직원이 곧바로 기계의 동전 재고를 기준 재고로 되돌린다.

이 기계를 시뮬레이션해서 기계가 손님에게 더 준 금액이 얼마인지 구하라. 기계는 여러 거래를 순서대로 처리하고, 기준 재고에서 시작한다. 손님이 넣은 동전은 거스름돈을 계산하기 전에 기계 재고에 더해진다. 기계가 가질 수 있는 동전 개수에는 제한이 없다. 손님에게 지급한 동전은 재고에서 빠진다. 손님은 판매 금액 이상을 내며, 더 냈다면 기계가 그 차액을 거슬러 준다. 손님이 넣은 동전 중 가장 큰 액면은 올바른 거스름돈보다 크다는 것이 보장된다.

첫째 줄에 기준 재고의 액면별 동전 개수 $C_1$, $C_2$, $C_5$, $C_{10}$, $C_{20}$, $C_{50}$ ($0 \le C_i \le 100$)이 주어진다.

둘째 줄에 처리할 거래의 수 $T$ ($1 \le T \le 1000$)가 주어진다.

다음 $T$개의 줄에 거래가 주어진 순서대로 하나씩 주어진다. 각 줄에는 정수 일곱 개가 있다. 판매 금액 $V$ ($1 \le V \le 99$)와 손님이 넣은 액면별 동전 개수 $d_1$, $d_2$, $d_5$, $d_{10}$, $d_{20}$, $d_{50}$ ($0 \le d_i \le 100$)이다.

모든 거래를 처리하는 동안 기계가 더 지급한 금액의 합을 센트 단위로 출력한다.