Summer Hand Fan
InterviewTime limit1sMemory limit1024 MB
For each fan compute the price plus the sum C + 2C + ... + mC for the number of K-hour intervals fully completed during the walk Q, then output the cheapest fan index.
- Level
Easy3 of 10
- Topics
- Math, Implementation, Array, Brute force
- Solved
- No attempts yet
Problem
Hyeonseok, who lives in Dasol Hall at the Catholic University of Korea, has come to B-Mart to buy a hand fan so he can get through the summer. The store displays N hand fans, numbered 1 through N, and every one of them works in a special way.
Once a hand fan is turned on, you must pay an additional cost every K hours for it to keep spinning. The cost the fan demands is C after K hours pass, 2✕C after 2✕K hours pass, and T✕C after T✕K hours pass, where T is a positive integer.
For example, suppose a hand fan costs 500 won and has an additional cost of 100 won every 3 hours, and the trip home takes 12 hours. Then you pay 100 won at 3 hours, 200 won at 6 hours, and 300 won at 9 hours, and at 12 hours you have arrived home, so no additional cost arises and you turn the fan off. The total is 600 won in additional costs plus the 500 won fan price, for 1,100 won.
Hyeonseok has decided that he simply cannot make it home without a hand fan, so he will buy exactly one fan. Given the time it takes him to walk home, help him choose the fan that gets him home safely with the least spending on the way.
Input
The first line gives two integers: the number of hand fans on display N(1 ≤ N ≤ 10,000) and the time it takes Hyeonseok to walk home Q(1 ≤ Q ≤ 1,000,000).
Lines 2 through N+1 each give three integers P, K, C, where P(0 ≤ P ≤ 100,000) is the price of the hand fan, K(1 ≤ K ≤ 1,000,000) is the time interval at which additional costs are due, and C(1 ≤ C ≤ 1,000,000) is the base value of the additional cost.
Output
Among the N hand fans, print the number of the fan Hyeonseok must buy to reach home at minimum cost, along with the cost required, separated by a space. If there are several answers, print the one with the smaller fan number.
Whichever fan is used, the required cost is less than 2^63-1.