Fewest Substrings Under Limit

You are given a string s consisting of digits '1' to '9', and an integer k.

Split s into contiguous substrings so that:

• every character of s belongs to exactly one substring, and
• the numeric value of every substring (the substring read as a base-10 integer) is at most k.

Return the minimum number of substrings in such a split, or -1 if no valid split exists.

Examples

Example 1

Input: s = "165462", k = 60
Output: 4
Explanation: Splitting into "16", "54", "6", "2" keeps every value at most 60, and no split with fewer than 4 substrings works.

Example 2

Input: s = "238182", k = 5
Output: -1
Explanation: The digit 8 alone already exceeds 5, so no valid split exists.