K. Пришёл Демид и всё проверил
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды ночью Демид решил проверить посылки ЛКШат из параллели B' и ужаснулся. Очередь была ужасно длинной и некрасивой. Демид определяет красоту очереди следующим образом: он выписывает в строчку номера групп ЛКШат, сделавших посылки (всего в параллели B' четыре группы: B6 - B9), в том же порядке, в котором посылки были сделаны, в результате чего получается некоторое число, чем больше полученное число, тем более красива очередь для Демида.

Демид не может сделать очередь из посылок короче, но может сделать её красивее. Для этого он может менять две посылки, стоящие рядом в очереди местами. Чтобы поменять местами посылки ЛКШат из групп $$$i$$$ и $$$j$$$, Демиду нужно потратить $$$c_{i, j}$$$ секунд. Через $$$K$$$ секунд Демид должен будить ЛКШат.

Помогите Демиду — определите самую красивую очередь, которую он может сделать не более, чем за $$$K$$$ секунд.

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

В первой строке содержатся два числа $$$N$$$ и $$$K$$$ ($$$1 \le N \le 10^5$$$, $$$0 \le K \le 10^9$$$) — количество посылок в очереди и количество секунд до подъёма соответственно. Во второй строке задана строка $$$s$$$ — очередь из посылок ($$$s_i$$$ — номер группы школьника $$$i$$$, $$$6 \le s_i \le 9$$$). Далее задана матрица $$$c$$$ размера $$$4 \times 4$$$: $$$c_{i, j}$$$ — стоимость обмена местами посылки школьника из групп $$$i + 5$$$ и $$$j + 5$$$ ($$$0 \le c_{i, j} \le 10^9$$$).

Обратите внимание, что матрица $$$c$$$ симметрична относительно диагонали, то есть $$$c_{i, j} = c_{j, i}$$$.

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

Выведите единственное число — максимально красивую очередь, которую сможет сделать Демид, в том же формате, что и во входных данных.

Пример
Входные данные
6 2
999789
1 1 1 1
1 1 1 1
1 1 1 3
1 1 3 1
Выходные данные
999897