Гонки "мусорщик идёт на охоту" решили организовать для участников соревнования по программированию. Вдобавок к начальной и конечной точке гонок существуют еще n (n ≤ 20) других мест которые можно посетить. В каждом месте i (1 ≤ i ≤ n) находится задание, выполнение которого принесет Вам pi очков. Для выполнения задания требуется ti минут. Каждое задание может быть выполнено только один раз, так что участник не может вернуться в одно и то же место более одного раза. После начала гонок нельзя вернуться в точку старта, гонки завершаются как только будет достигнута конечная точка.

Гонки должны завершиться за t минут. То есть время между стартом и прибытием в конечную точку не должно превышать t минут. К тому же некоторые задачи имеют предельный срок (дедлайн) di, то есть задача должна быть выполнена не позже чем через di минут после выхода из стартовой точки. Если участник прибывает в место i, то задача в точке i обязательно должна быть выполнена. Если участник прибывает в точку поздно и не может выполнить задачу в ней до завершения дедлайна, тогда он вообще не имеет права заходить в эту точку.

Найдите наибольшее количество очков, которое можно получить от выполнения задач.

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

Первая строка содержит два натуральных числа n и t (t ≤ 1440). Каждая из следующих n строк содержит три целых числа pi (1 ≤ pi ≤ 100), ti (1 ≤ ti ≤ 1440) и di (-1 ≤ di ≤ 1440). Если di = -1, то предельного срока для выполнения i-ой задачи не существует. Последние n + 2 строки содержат n + 2 неотрицательных целых числа. Число в i-ой строке и j-ом столбце содержит количество минут (≤ 1440) которое требуется чтобы дойти от места i к месту j. Индексы начальной и конечной точки соответственно равны n + 1 и n + 2.

Гарантируется, что время путешествия от каждого места до него же самого равно 0, но время путешествия между двумя точками в разных направлениях может быть различным (в одну сторону может быт подъем, а в обратную тогда будет спуск).

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

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

Если наибольшее количество очков равно 0, то во второй строке вместо индексов задач следует вывести пустую строку.