Dan is playing a game with Ben. Ben gives Dan a long string S, and Dan needs to compress S to a list or short strings: s[1], s[2], ..., s[N]. S only contains lowercase letters. Each s[i] can contain lowercase letters and digits, but only digits between i+1 and N, inclusive, are allowed for s[i]. For example, when N = 4, allowed digits for s[2] will be '3' and '4'.
In order to decompress such a list of strings into a single string, we'll apply string decompress algorithm for each string one by one, in reverse order (from s[N] to s[1]). The decompressing algorithm for a string is easy: just replace each digit in the string by the corresponding decompressed string with that digit as index. That is to say, for digit i in the string, it will be replaced by the decompressed string s[i]. Because we are applying decompressing algorithm in reverse order, s[i] will always be decompressed before it is used to replace a digit in other strings. When all the strings are decompressed, the decompressed string of s[1] will be the final result. If the decompressing result is S, we say S can be compressed to this list of strings.
Now Ben decides the number of short strings Dan can use (N), as well as the length limit for each short string. Dan needs to decide whether it is possible to compress S to N short strings under this limit.