비닐봉지

어느 백화점은 쓰레기를 줄이려고 손님에게 장바구니 사용을 권한다. 그래도 장바구니 없이 오는 손님이 있어서, 백화점은 구매 금액에 따라 비닐봉지를 한 장씩 무료로 준다.

비닐봉지는 세 가지 크기이고 견디는 무게가 다르다.

1. 소형 봉지는 500그램까지 담는다.
2. 중형 봉지는 1250그램까지 담는다.
3. 대형 봉지는 2000그램까지 담는다.

무료로 주는 봉지는 구매 금액 합계로 정한다.

1. 합계가 500바트 미만이면 소형 봉지 한 장을 준다.
2. 합계가 500바트 이상 1000바트 미만이면 중형 봉지 한 장을 준다.
3. 합계가 1000바트 이상이면 대형 봉지 한 장을 준다.

무게가 2000그램을 넘는 상품은 어떤 봉지도 감당하지 못하므로 손님이 직접 들고 간다. 나머지 상품은 모두 봉지에 담아야 한다. 상품 하나를 두 봉지에 나눠 담을 수는 없고, 한 봉지에는 담은 상품 무게의 합이 그 봉지가 견디는 무게 이하이면 몇 개든 담을 수 있다.

무료 봉지 한 장으로 모자라면 손님이 봉지를 사야 한다. 소형은 5바트, 중형은 12바트, 대형은 20바트이고 수량 제한은 없다.

무게가 2000그램 이하인 상품을 모두 담으려면 봉지 값으로 얼마를 내야 하는지, 그 최솟값을 구하라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 100$)가 주어진다.

각 테스트 케이스의 첫 줄에는 손님이 산 상품 종류의 수 $N$ ($1 \le N \le 10$)이 주어진다. 이어지는 $N$개 줄에는 정수 세 개 $A$, $B$, $C$가 주어진다. $A$는 상품 한 개의 가격, $B$는 산 개수, $C$는 상품 한 개의 무게(그램)이다. ($1 \le A \le 1000000$, $1 \le B \le 2$, $1 \le C \le 100000$)

구매 금액 합계는 모든 줄의 $A \times B$를 더한 값이다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 무게가 2000그램 이하인 상품을 모두 담는 데 드는 봉지 값의 최솟값이다.