First Number With Digit Sum k

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given $l,r,k$, find the smallest integer $x$ in inclusive interval $[l,r]$ whose decimal digit sum equals $k$, or -1 if absent. The digit sum of 0 is 0. Stop the outer search loop at the first match.

Input

One line contains $l,r,k$ with $0\le l\le r\le100000$ and $0\le k\le100$.

Output

Print the smallest matching number, or -1.

Subtasks

• Subtask 1 (20%): $0\le l\le r\le 100$; $0\le k\le100$.

• Subtask 2 (30%): $0\le l\le r\le 5000$; $0\le k\le100$.

• Subtask 3 (50%): $0\le l\le r\le 100000$; $0\le k\le100$.

Examples

Example 1

Input:

10 20 2

Output:

11

Explanation:

Within [10,20], the first number with digit sum 2 is 11.

Example 2

Input:

0 0 0

Output:

0

Explanation:

Within [0,0], the first number with digit sum 0 is 0.

Example 3

Input:

99 100 50

Output:

-1

Explanation:

Within [99,100], the first number with digit sum 50 is -1.