Варп-швидкість II

Вхідні дані

Вхідні дані складаються з $4$ частин, розділених порожнім рядком.

Перша частина визначає розміри станів варп-двигуна та типів стрибків.

• Вона містить лише один рядок з $2$ числами, розділеними пробілом. Ці $2$ числа є:

  • Розмір станів варп-двигуна ($N$), який належить до діапазону від $1$ до $100$.

    • Ідентифікатори станів мають значення від $0$ до N - 1.

    • Перший стан (ідентифікатор $0$) — це неактивний стан. У цьому стані варп-двигун не може виконувати жодних стрибків. (Саме з цього стану починається та завершується будь-яка послідовність станів у відповіді.)

  • Кількість типів стрибків ($H$), що належить до діапазону від $1$ до $1000$.

    • Ідентифікатори стрибків мають значення від $0$ до H - 1.

Друга частина — таблиця, що вказує енергію перемикання між станами варп-двигуна. Її розмір — $N$ рядків та $N$ стовпців, тобто N^2 значень енергії.

• Є $N$ рядків. Кожен рядок містить $N$ енергетичних значень. Усі числа знаходяться в межах від $1$ до $100$.

• Кожне значення енергії індексується за рядком та стовпцем (спочатку $0$) — це ідентифікатори поточного й наступного стану відповідно.

  • Наприклад, значення з індексами (рядок $5$, стовпець $0$) — це енергія для переходу зі стану № $5$ у стан $0$. (Це перше число у шостому рядку.)

Третя частина — таблиця, що визначає енергоспоживання для виконання стрибків у кожному зі станів варп-двигуна.

Розмір таблиці — $N$ рядків на $H$ стовпців, тобто N \times H чисел.

• Є $N$ рядків. Кожен рядок містить по $H$ енергетичних значень (у межах від $1$ до $100$).

• Значення індексуються за рядком (ідентифікатор стану) та стовпцем (ідентифікатор стрибка), обидва починаються з $0$.

  • Наприклад, значення з індексами (рядок $1$, стовпець $9$) — це витрати енергії для варп-двигуна в стані $1$ для виконання стрибка $9$. (Це десяте число у другому рядку.)

  • Зверніть увагу, що у першому рядку таблиці цієї частини, який відповідає стану $0$ (неактивний стан), усі значення дорівнюють нулю. Це означає, що у цьому стані не можна виконувати жодних стрибків.

Четверта частина — набір послідовностей стрибків; їх кількість від $1$ до $1000$.

• Кількість рядків — від $1$ до $1000$.

• Кожен рядок у цій частині містить одну послідовність стрибків.

• Кількість стрибків у послідовності — від $1$ до $1000$.

• Кожен стрибок позначається числом від $0$ до H - 1 та розділяється пробілом.

Порожній рядок після четвертої частини є закінченням введення.

Вихідні дані

Для кожної послідовності стрибків із четвертої частини введення ви повинні надрукувати у відповідь $2$ частини:

• У першому рядку — загальну мінімальну кількість енергії.

• У наступному рядку — розв'язок: послідовність станів варп-двигуна, відповідну заданій послідовності стрибків (довжини мають співпадати). Якщо існує декілька оптимальних рішень із однаковими витратами енергії, виведіть ту, у якій номери станів йдуть у найменшому порядку при ліво-правому порівнянні.

Додаткові пояснення

У першому прикладі (рішення для $13$-го рядка введення) мінімальна енергія становить $9$. Послідовність станів: $[32]$, або [0-\ 3\ 2\ -0]. Відбулося $3$ перемикання: 0 \to 3, 3 \to 2, 2 \to 0, на які витрачено 1 + 1 + 2 = 4. І два стрибки ($0$ та $4$) виконані у станах $3$ й $2$ відповідно (4 + 1 = 5). Сумарна енергія: 4 + 5 = 9.

У останньому прикладі мінімальна енергія — $23$. Розв'язок — [0-\ 1\ 1\ 2\ 3\ -0], що витрачає всього $23$ енергії.

Приклади