동의대학교 수덕전에는 음료 자판기가 있다. 이 자판기는 구식이어서 여러 개의 음료를 구매하기 위해서는 매우 번거롭다. 왜냐하면 돈 넣고 하나 뽑고, 또 돈 넣고 하나 뽑고,… 이런 식으로 여러 개를 구매해야 하기 때문이다. 그래서 도훈이는 새로운 자판기 프로그램을 만들어서 좀 더 편리한 자판기가 되도록 해보고 싶다.

새로운 자판기 프로그램은 사고 싶은 음료의 종류 버튼을 누른 후 다시 원하는 개수만큼의 숫자를 입력하고 확인을 누르고, 또 다른 음료의 종류 버튼을 누른 후 다시 원하는 개수만큼의 숫자를 입력하고 확인을 누르고,… 이런 식으로 반복한 후 마지막에 완료 버튼을 누르면 총 가격을 알려주고 그 가격만큼의 돈을 투입하면 음료수가 모두 나오는 구조이다. 

자판기 완료 버튼을 눌렀을 때 선택한 음료수들의 총 가격을 알려주고, 최소 금액의 거스름돈을 받기 위한 투입 금액, 거스름돈 액수, 그리고 거스름돈 동전 개수가 최소가 되도록 하는 동전별 갯수를 출력하는 프로그램을 작성하시오. 사용 가능한 지폐는 10,000원권, 5,000원권, 1,000원권의 3가지 종류이고 거스름돈은 500원, 100원의 2가지 동전으로만 나오는 것으로 가정한다.

첫 줄에 테스트케이스의 수가 들어온다.

그 다음 줄에 음료수의 종류(n_menu)가 입력된다. ( 1 <= n_menu <= 10)

그 다음 줄부터 음료의 종류와 가격(price)이 n_menu 줄 입력된다. ( 500 <= price <= 5,000)  모든 음료의 가격은 100의 배수이다.

그 다음 줄에 구매하고자 하는 음료 종류의 개수(drink_num)가 입력된다. 1 <= drink_num <= n_menu <= 10)

다음 줄부터 선택한 음료의 종류와 구매하고자 하는 개수(buy_num)가 drink_num 줄 입력된다.(1 <= buy_num <= 5)


* 음료수의 이름은 중복되지 않으며, 이름의 최대 길이는 영어 15자이다.