Modest Substrings

### 题目描述 给出$l,r,n$，定义一个数的权值为数对$(i,j)(i < j)$的数量，满足$i$到$j$位的数拿出来得到的数的值在$[l,r]$内。 试求一个$n$位大数（包含前导$0$的子串不计入答案。），使得其权值最大。 ### 输入格式 三行，每行一个正整数，第一行为$l$，第二行为$r$，第三行为$n$ ### 输出格式 两行，第一行表示最大权值，第二行表示权值等于最大权值的最小大数。 ### 数据范围 $1 \leq l,r \leq 10^{800} , 1 \leq n \leq 2000$

You are given two integers $ l $ and $ r $ . Let's call an integer $ x $ modest, if $ l \le x \le r $ . Find a string of length $ n $ , consisting of digits, which has the largest possible number of substrings, which make a modest integer. Substring having leading zeros are not counted. If there are many answers, find lexicographically smallest one. If some number occurs multiple times as a substring, then in the counting of the number of modest substrings it is counted multiple times as well.

The first line contains one integer $ l $ ( $ 1 \le l \le 10^{800} $ ). The second line contains one integer $ r $ ( $ l \le r \le 10^{800} $ ). The third line contains one integer $ n $ ( $ 1 \le n \le 2\,000 $ ).

In the first line, print the maximum possible number of modest substrings. In the second line, print a string of length $ n $ having exactly that number of modest substrings. If there are multiple such strings, print the lexicographically smallest of them.

1
10
3

3
101

1
11
3

5
111

12345
12346
6

1
012345

In the first example, string «101» has modest substrings «1», «10», «1». In the second example, string «111» has modest substrings «1» ( $ 3 $ times) and «11» ( $ 2 $ times).