26218번 - 생산 시스템 관리 스페셜 저지

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

작업 $i$는 기계 $i$를 가동함으로써 이루어진다. 기계 $i$를 $1$대 갖췄을 때 작업 $i$가 올바르게 작동할 확률은 $p_{i} / 100$이며, 여기에 기계 $i$를 추가로 한 대 더 구매할 때마다 작업 $i$가 올바르게 작동할 확률이 $a_{i} / 100$ 늘어난다. 단, 기계 $i$를 아무리 많이 구매해도 작업 $i$가 올바르게 작동할 확률은 $1$을 넘을 수 없다.

예를 들면, 작업 1과 작업 2가 존재하면서 $p_{1} = 40$, $p_{2} = 60$, $a_{1} = 15$, $a_{2} = 10$인 경우, 기계 1과 기계 2를 각각 한 대씩 있을 때 모든 작업이 올바르게 작동할 확률 $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$의 대수를 차례로 공백으로 구분하여 출력한다.

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