Однажды ночью Демид решил проверить посылки ЛКШат из параллели 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
