생산 시스템 관리

겨울 숲의 나라에는 $N$종류의 작업으로 이루어진 생산 시스템이 있다. 이 시스템에서 모든 작업이 올바르게 작동하도록 하려고 한다.

작업 $i$는 기계 $i$를 가동해서 수행한다. 기계 $i$가 1대 있을 때 작업 $i$가 올바르게 작동할 확률은 $p_{i} / 100$이다. 기계 $i$를 한 대 추가로 구매할 때마다 이 확률은 $a_{i} / 100$만큼 늘어난다. 다만 기계 $i$를 아무리 많이 구매하더라도 작업 $i$가 올바르게 작동할 확률은 $1$을 넘을 수 없다.

예를 들어 작업 1과 작업 2가 있고 $p_{1} = 40$, $p_{2} = 60$, $a_{1} = 15$, $a_{2} = 10$이라고 하자. 기계 1과 기계 2가 각각 1대씩 있을 때 모든 작업이 올바르게 작동할 확률 $P$는 $0.4 \times 0.6 = 0.24$이다. 그러나 기계 1을 2대, 기계 2를 1대 추가로 구매해서 각각 총 3대와 2대를 갖추면 $P$는 $(0.4 + 0.15 \times 2) \times (0.6 + 0.1 \times 1) = 0.49$로 높아진다. 기계 $i$의 가격이 $c_{i}$일 때, 총 비용을 $B$ 이하로 사용하면서 $P$를 최대화하려면 어떻게 해야 하는가?

초기 상태에는 모든 종류의 기계가 한 대씩 있다.

첫 줄에 작업의 종류 수를 나타내는 정수 $N$ ($1 \leq N \leq 9$)과 비용 $B$ ($0 \leq B \leq 30,000$)가 주어진다.

다음 $N$개의 줄에는 기계 $i$에 대한 $p_{i}$, $a_{i}$, $c_{i}$가 공백으로 구분된 정수로 주어진다. ($1 \leq p_{i}, a_{i} \leq 99$, $1 \leq c_{i} \leq 30,000$)

첫 번째 줄에 총 비용을 $B$ 이하로 사용했을 때 $P$의 최댓값에 $10^{2N}$을 곱한 값을 출력한다. 이 값은 항상 정수이다.

두 번째 줄에는 기계 $i$마다 추가로 구매해야 하는 대수를 차례로 공백으로 구분하여 출력한다.

가능한 방법이 여럿이면 그중 아무거나 출력한다.