B. Страшный сон Егора
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод или input.txt
вывод
стандартный вывод или output.txt

Егор — школьник. 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