Minimizing the Maximum k‐Digit Substring

Given nine non‐negative integers \(d_1, d_2, \ldots, d_9\) representing the frequency of digits \(1,2,\ldots,9\) respectively, let \(s = \sum_{i=1}^9 d_i\). Construct a positive integer \(x\) with exactly \(s\) digits (in base 10) such that for each \(1 \le i \le 9\), digit \(i\) appears exactly \(d_i\) times in \(x\).

Now, consider the decimal representation of \(x\) as a string. For a given integer \(k\) (with \(1 \le k \le s\)), extract every contiguous substring of length \(k\) (there will be \(s-k+1\) such substrings). Convert each substring to an integer, yielding values \(y_1, y_2, \ldots, y_{s-k+1}\). Your task is to choose an arrangement for \(x\) so that the quantity

[ M = \max{y_1, y_2, \ldots, y_{s-k+1}} ]

is minimized. Output this minimum possible value of \(M\).

Note: Since the digits available are only from 1 to 9, \(x\) will not have any leading zeros.

inputFormat

The input consists of two lines.

• The first line contains 9 space‐separated non‐negative integers: \(d_1, d_2, \ldots, d_9\).
• The second line contains a single integer \(k\) (\(1 \le k \le s\), where \(s=\sum_{i=1}^9 d_i\)).

outputFormat

Output a single integer: the minimum possible value of \(\max\{y_1,y_2,\ldots,y_{s-k+1}\}\) over all valid constructions of \(x\).

sample

1 0 0 0 0 0 0 0 0
1

1