Егор — школьник. Cовсем скоро ему предстоит участвовать в региональном этапе Всероссийской олимпиады школьников по информатике. К олимпиаде он готов, полностью уверен в победе в регионе, но чтобы пройти в следующий, заключительный этап, ему нужно постараться.
Накануне перед олимпиадой ему приснился страшный сон: Егор не набрал необходимые T проходных баллов по итогу олимпиады, а значит на заключительный этап он поедет только по квоте! Об отношении к квотникам на заключительном этапе Егор знает не понаслышке, поэтому он просит вас о помощи.
Помимо проходного балла T — минимального количества баллов, которое нужно набрать, ему приснилось, что на олимпиаде будет N задач, по каждой можно набрать целый балл от 0 до 100, при этом в i-й задаче можно будет набрать только балл, кратный ki.
Егору не приснились сами задачи, но приснились затраты энергии si — сколько требуется энергии на прочтение задачи, и ci — сколько потребуется энергии чтобы набрать по задаче один балл. Естественно, нельзя набирать баллы по задаче, не прочитав её.
Егор хочет набрать как минимум T баллов, но при этом хочет потратить суммарно как можно меньше энергии, чтобы потом смело можно было заявлять, что он писал олимпиаду на расслабоне.
Определите минимальное количество энергии, необходимое Егору, а также сколько баллов нужно набрать по каждой задаче для того, чтобы достичь требуемого результата, затратив минимальное количество энергии.
В первой строке содержатся два целых числа N и T (1 ≤ N ≤ 100; 1 ≤ T ≤ 100 × N).
В следующих N строках содержится по три числа si, ci и ki для каждой задачи (1 ≤ si, ci ≤ 105; 1 ≤ ki ≤ 100; ki — делитель числа 100).
В первую строку выведите минимальное количество энергии, которого хватит для достижения цели Егора.
Во второй строке выведите N чисел bi через пробел — баллы, которые нужно набирать по каждой задаче. Каждое bi должно делиться на ki, а также должно выполняться неравенство 0 ≤ bi ≤ 100.
Если существует несколько решений, выведите любое.
3 166
10 5 1
1 1 10
15 4 25
406
16 100 50
| Название |
|---|


