Minimizing Difference in a Variable-Radix Number System

In a conventional numeral system, each digit position has a fixed radix. In this problem we deal with a magical numeral system, called the X-base system, in which each digit position may have a different radix. The value of an X-base number is computed as follows. Let an X-base number be represented as a sequence of digits \(d_{m-1}d_{m-2}\ldots d_0\) (with \(d_0\) being the least significant digit). Suppose that the radix for the digit at position \(i\) (starting from \(0\)) is \(b_i\), then its decimal value is given by

$$V = \sum_{i=0}^{m-1} \left(d_i\prod_{j=0}^{i-1}b_j\right), $$

with the convention that \(\prod_{j=0}^{-1}b_j = 1\). However, the twist is that the radix for each digit is not fixed. Instead, the following rules apply:

• The radix for the least significant digit (position \(0\)) is fixed to \(2\) (i.e. binary), so \(b_0=2\).
• For every other digit at position \(i \ge 1\), its radix \(b_i\) can be chosen arbitrarily subject to \(b_i \in [L_i, N]\), where \[ L_i = \max\{a_i, b_i\} + 1, \] and \(N\) is given.

Here, the two numbers \(A\) and \(B\) are given in this X-base representation. You are allowed to choose the radices \(b_i\) (for every digit position \(i \ge 1\)) under the above constraints so that both numbers are legally represented (i.e. each digit must be less than its corresponding radix), and the expression

$$A - B = \sum_{i=0}^{m-1} \left((a_i - b_i)\prod_{j=0}^{i-1}b_j\right) $$

is minimized. Compute the minimum possible value of \(A-B\). Note that the answer may be negative.

Example: Suppose that a certain \(X\)-base system uses radices \(b_0=2, b_1=10, b_2=8\). Then, the X-base number 321 (with digits \(3\), \(2\), and \(1\) from most to least significant) converts to decimal as

$$1 + 2 \times 2 + 3 \times (2\times10) = 1 + 4 + 60 = 65. $$

inputFormat

The input consists of three lines:

1. The first line contains the string \(A\) (its X-base representation).
2. The second line contains the string \(B\) (its X-base representation). Note that \(A\) and \(B\) may have different lengths. For positions that exceed the length of a number, assume the digit is \(0\).
3. The third line contains an integer \(N\) (\(2 \le N \le 10\)), which is the maximum allowed radix for each digit position (except that the least significant digit is fixed to radix \(2\)).

You may assume that the digits in \(A\) and \(B\) are valid decimal digits (0–9) and that there exists at least one valid choice of radices such that both \(A\) and \(B\) are legal in the X-base system.

outputFormat

Output a single integer — the minimum possible value of \(A-B\) after optimally choosing the radices under the given constraints.

sample

101
11
10

2