Lemonade Stand

You run a lemonade stand and know exactly how many cups of lemonade customers will want on each day you operate. You do not want to turn anyone away, so you must always have enough lemons and sugar to make the cups needed each day. The cost of lemons and sugar changes daily, so you choose which days to buy each ingredient and how much to buy. Lemons are sold individually, and sugar is sold in five pound bags. (There are 16 ounces in one pound.) On a day you buy ingredients, you buy them in the morning, before any sales. You are an early riser, so you can get to the store and back before customers arrive. You can buy as little or as much as you want on any day, since you have enough startup money to buy any amount. Leftover lemons and sugar carry over to the next day. Find the minimum cost of the lemons and sugar needed so that no customer is turned away.

The first line contains n (1 ≤ n ≤ 100), the number of test cases. Each test case starts with three positive integers d (1 ≤ d ≤ 1000), the number of days, x (1 ≤ x ≤ 10), the number of lemons needed for one cup, and s (1 ≤ s ≤ 10), the number of ounces of sugar needed for one cup. The next d lines describe days 1 through d. Each line has three integers c (1 ≤ c ≤ 1000), the number of cups sold that day, pl (1 ≤ pl ≤ 50), the price of one lemon in cents that day, and ps (1 ≤ ps ≤ 500), the price of a five pound bag of sugar in cents that day.

For each test case, print the minimum cost of supplies in cents needed so that no customer who wants a cup of lemonade is turned away.