13068번 - Funfair 다국어

We are going to a funfair where there are n games G₁, . . . , G_n. We want to play k games out of the n games, and we can choose the order in which we play them—note that we cannot play any game more than once. We have to specify these k games and their order before starting any game.

At each point in time, we have some amount of money, which we use in playing the games. At the beginning, we have x₀ Oshloobs of money. If before playing game G_i, we have x Oshloobs and we win in G_i, our money increases to x+A_i for some A_i ≥ 0. If we have x Oshloobs before playing game G_i and we lose in G_i, we lose L_i percent of x. The probability that we win game G_i (independently of other games) is P_i percents.

The goal is to play k of the games in such an order to maximize the expected amount of money we end up with after playing all k selected games in that order.

There are multiple test cases in the input. The first line of each test case contains three space-separated integers n, k, and x₀ (1 ≤ k ≤ n ≤ 100, 0 ≤ x₀ ≤ 10⁶). Each of the next n lines specifies the properties of game G_i with three space-separated integers A_i, L_i, and P_i (0 ≤ A_i, L_i, P_i ≤ 100). The input terminates with a line containing 0 0 0 which should not be processed.

For each test case, output a single line containing the maximum expected amount of our final money rounded to exactly two digits after the decimal point.