레모네이드 가판대
면접 대비시간 제한1초메모리 제한1024 MB
날마다 필요한 레모네이드 컵 수와 레몬, 설탕 가격이 주어질 때, 손님에게 모두 음료를 줄 수 있는 최소 재료비를 구합니다.
문제
레모네이드 가판대를 운영하며, 영업하는 각 날에 손님이 몇 잔을 원할지 정확히 알고 있다. 손님을 돌려보내고 싶지 않으므로, 매일 필요한 잔 수를 만들 만큼의 레몬과 설탕을 항상 갖추어야 한다. 레몬과 설탕의 가격은 날마다 바뀌므로, 어느 날 무엇을 얼마나 살지 직접 골라야 한다. 레몬은 낱개로 살 수 있고, 설탕은 5파운드 봉지 단위로 판매된다. (1파운드는 16온스다.) 재료를 사기로 한 날에는 판매가 시작되기 전 아침에 산다. 일찍 일어나는 편이라 손님이 오기 전에 가게에 다녀올 수 있다. 시작 자금이 충분하므로 어느 날이든 원하는 만큼 얼마든지 살 수 있다. 남은 레몬과 설탕은 다음 날로 이월된다. 어떤 손님도 돌려보내지 않도록 필요한 레몬과 설탕의 최소 비용을 구하라.
입력
첫 줄에 테스트 케이스의 수 n (1 ≤ n ≤ 100)이 주어진다. 각 테스트 케이스의 첫 줄에는 양의 정수 세 개가 공백으로 구분되어 주어진다. d (1 ≤ d ≤ 1000)는 영업 일수, x (1 ≤ x ≤ 10)는 한 잔을 만드는 데 필요한 레몬 개수, s (1 ≤ s ≤ 10)는 한 잔을 만드는 데 필요한 설탕의 온스 수다. 이어서 d개의 줄이 1일차부터 d일차까지를 차례로 나타낸다. 각 줄에는 정수 세 개가 공백으로 구분되어 주어진다. c (1 ≤ c ≤ 1000)는 그날 팔린 잔 수, pl (1 ≤ pl ≤ 50)은 그날 레몬 한 개의 가격(센트), ps (1 ≤ ps ≤ 500)는 그날 5파운드 설탕 봉지의 가격(센트)이다.
출력
각 테스트 케이스에 대해, 레모네이드를 원하는 손님을 한 명도 돌려보내지 않는 데 필요한 재료의 최소 비용을 센트 단위로 출력한다.