Дано целое число $$$x$$$ и строка $$$s$$$, состоящая из цифр от $$$1$$$ до $$$9$$$ включительно.
Подстрокой строки называется последовательная подпоследовательность этой строки.
Пусть $$$f(l, r)$$$ будет равно сумме цифр в подстроке $$$s[l..r]$$$.
Назовем подстроку $$$s[l_1..r_1]$$$ $$$x$$$-простой, если
Разрешено удалять любые символы из строки. Если вы удаляете символ, то две полученные части строки склеиваются, не меняя порядок.
Какое минимальное количество символов надо удалить из строки, чтобы она не содержала $$$x$$$-простых подстрок? Если $$$x$$$-простых подстрок нет в данной строке $$$s$$$, то выведите $$$0$$$.
В первой строке записана строка $$$s$$$ ($$$1 \le |s| \le 1000$$$). $$$s$$$ содержит только цифры от $$$1$$$ до $$$9$$$ включительно.
Во второй строке записано одно целое число $$$x$$$ ($$$1 \le x \le 20$$$).
Выведите одно целое число — минимальное количество символов, которые надо удалить из строки, чтобы она не содержала $$$x$$$-простых подстрок? Если $$$x$$$-простых подстрок нет в данной строке $$$s$$$, то выведите $$$0$$$.
116285317 8
2
314159265359 1
2
13 13
0
3434343434 7
5
В первом примере в строке две $$$8$$$-простых подстроки «8» и «53». Можно удалить данные символы, чтобы избавиться от обеих: «116285317». Полученная строка «1162317» не содержит $$$8$$$-простых подстрок. Также можно удалить такие символы: «116285317».
Во втором примере необходимо просто удалить обе единицы.
В третьем примере нет $$$13$$$-простых подстрок. В нем вообще нет подстрок с суммой цифр равной $$$13$$$.
В четвертом примере в строке не должно быть ни «34», ни «43». Поэтому необходимо удалить либо все тройки, либо все четверки. Их по $$$5$$$ штук, поэтому можно удалить любые из них.
