Production System Management

In the land of the winter forest, a production system is made up of $N$ kinds of jobs. The goal is for every job in this system to work correctly.

Job $i$ is carried out by running machine $i$. When there is one machine $i$, the probability that job $i$ works correctly is $p_{i} / 100$. Each additional machine $i$ purchased raises that probability by $a_{i} / 100$. However, no matter how many machines $i$ are bought, the probability that job $i$ works correctly cannot exceed $1$.

For example, suppose there are jobs 1 and 2 with $p_{1} = 40$, $p_{2} = 60$, $a_{1} = 15$, and $a_{2} = 10$. When there is one machine each for machines 1 and 2, the probability $P$ that every job works correctly is $0.4 \times 0.6 = 0.24$. However, if you buy 2 more of machine 1 and 1 more of machine 2, giving 3 and 2 machines in total, $P$ improves to $(0.4 + 0.15 \times 2) \times (0.6 + 0.1 \times 1) = 0.49$. If machine $i$ costs $c_{i}$, how can $P$ be maximized with total cost at most $B$?

Initially, there is one machine of each kind.

The first line contains an integer $N$ ($1 \leq N \leq 9$), the number of job types, and an integer $B$ ($0 \leq B \leq 30,000$), the budget.

The next $N$ lines each contain integers $p_{i}$, $a_{i}$, and $c_{i}$ separated by spaces. ($1 \leq p_{i}, a_{i} \leq 99$, $1 \leq c_{i} \leq 30,000$)

On the first line, print the maximum possible value of $P$ multiplied by $10^{2N}$, using a total cost of at most $B$. This value is always an integer.

On the second line, print the number of additional machines to buy for each machine $i$ in order, separated by spaces.

If there are several ways, print any of them.