Страшный сон Егора

Егор — школьник, совсем скоро ему участвовать в региональном этапе Всероссийской олимпиады школьников по информатике. К олимпиаде он готов, полностью уверен в победе в регионе, но чтобы пройти в следующий, заключительный этап, ему нужно постараться.

Накануне перед олимпиадой ему приснился страшный сон: Егор не набрал необходимые T проходных баллов по итогу олимпиады, а значит на заключительный этап он поедет только по квоте! Об отношении с квотниками на заключительном этапе Егор знает не понаслышке, поэтому он просит вас о помощи.

Помимо проходного балла T — минимального количества баллов, которое нужно набрать, ему приснилось, что на олимпиаде будет N задач, по каждой можно набрать целый балл от 0 до 100, при этом в i-й задаче можно будет набрать только балл, кратный k_i.

Егору не приснились сами задачи, но приснились затраты энергии s_i — сколько требуется энергии на прочтение задачи, и c_i — сколько потребуется энергии чтобы набрать по задаче один балл. Естественно, нельзя набирать баллы по задаче, не прочитав её.

Егор хочет набрать как минимум T баллов, но при этом хочет потратить суммарно как можно меньше энергии, чтобы потом смело можно было заявлять, что он писал олимпиаду на расслабоне.

Определите минимальное количество энергии, необходимое Егору, а также для каждой задачи, какой балл по ней нужно набрать, чтобы достичь этого результата.

Входные данные

В первой строке входного файла INPUT.TXT содержатся два целых числа N и T (1 ≤ N ≤ 100; 1 ≤ T ≤ 100×N).

Выходные данные

В первую строку выходного файла OUTPUT.TXT выведите минимальное количество энергии, которого хватит для достижения цели Егора.

Если существует несколько решений, выведите любое.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]