Дивовижні перегони
Гонки "сміттяр йде на полювання" вирішили організувати для учасників змагання з програмування. Окрім початкової та кінцевої точок, є ще n (n ≤ 20) інших місць, які можна відвідати. У кожному місці i (1 ≤ i ≤ n) є завдання, виконання якого приносить p[i] очок. Для виконання завдання потрібно t[i] хвилин. Кожне завдання можна виконати лише один раз, тому учасник не може повернутися в одне й те саме місце більше одного разу. Після початку гонок не можна повертатися в точку старту, гонки завершуються, як тільки буде досягнута кінцева точка.
Гонки повинні завершитися за t хвилин. Тобто час між стартом і прибуттям у кінцеву точку не повинен перевищувати t хвилин. Деякі задачі мають крайній термін (дедлайн) d[i], тобто задача повинна бути виконана не пізніше ніж через d[i] хвилин після виходу з початкової точки. Якщо учасник прибуває в місце i, то задача в точці i обов'язково повинна бути виконана. Якщо учасник прибуває в точку пізно і не може виконати задачу в ній до завершення дедлайну, тоді він взагалі не має права заходити в цю точку.
Знайдіть найбільшу кількість очок, яку можна отримати від виконання задач.
Вхідні дані
Перша рядок містить два натуральних числа n і t (t ≤ 1440). Кожен з наступних n рядків містить три цілих числа p[i] (1 ≤ p[i] ≤ 100), t[i] (1 ≤ t[i] ≤ 1440) і d[i] (-1 ≤ d[i] ≤ 1440). Якщо d[i] = -1, то крайнього терміну для виконання i-ої задачі не існує. Останні n + 2 рядки містять n + 2 невід'ємних цілих числа. Число в i-му рядку і j-му стовпці містить кількість хвилин (≤ 1440), яке потрібно, щоб дійти від місця i до місця j. Індекси початкової та кінцевої точки відповідно дорівнюють n + 1 і n + 2.
Гарантується, що час подорожі від кожного місця до нього ж самого дорівнює 0, але час подорожі між двома точками в різних напрямках може бути різним (в один бік може бути підйом, а в зворотному тоді буде спуск).
Вихідні дані
У першому рядку виведіть максимальну кількість очок, яку можна заробити в гонках. У другому рядку виведіть список індексів задач, які слід виконати для досягнення цього максимуму. Індекси слід розділяти одним пробілом. Якщо максимум досягається на кількох множинах задач, то виведіть лексикографічно найменшу. Тобто якщо один і той самий максимум досягається на двох множинах, то індекс першої задачі у множині повинен бути найменшим. Якщо перші індекси у множинах рівні, то слід вибрати те, де другий індекс найменший, і так далі.
Якщо найбільша кількість очок дорівнює 0, то у другому рядку замість індексів задач слід вивести порожній рядок.