Plastic Bags

A department store wants less plastic waste, so it asks shoppers to bring a cloth bag. Some customers still arrive without one, so the store gives away one free plastic bag according to how much the customer spends.

The store keeps three bag sizes, and each one holds a different weight.

1. A small bag holds up to 500 grams.
2. A medium bag holds up to 1250 grams.
3. A large bag holds up to 2000 grams.

The total price of the purchase decides the free bag.

1. Under 500 baht, the customer gets one small bag.
2. From 500 baht up to but not including 1000 baht, the customer gets one medium bag.
3. At 1000 baht or more, the customer gets one large bag.

No bag can carry an item heavier than 2000 grams, so the customer takes such an item home by hand. Every other item has to go into a bag. One item cannot be split between two bags, and a bag takes any number of items as long as their combined weight stays within what the bag holds.

When the single free bag is not enough, the customer buys bags. A small bag costs 5 baht, a medium bag 12 baht, and a large bag 20 baht, and the store never runs out.

Find the smallest amount the customer can pay for bags while every item weighing at most 2000 grams goes into a bag.

The first line has the number of test cases $T$ ($1 \le T \le 100$).

The first line of each test case has the number of product types the customer bought, $N$ ($1 \le N \le 10$). Each of the next $N$ lines has three integers $A$, $B$, and $C$: the price of one unit, the number of units bought, and the weight of one unit in grams ($1 \le A \le 1000000$, $1 \le B \le 2$, $1 \le C \le 100000$).

The total price of the purchase is the sum of $A \times B$ over all lines.

For each test case print one integer on its own line: the smallest amount of baht the customer pays for bags so that every item weighing at most 2000 grams goes into a bag.