Số đầu tiên có tổng chữ số bằng k (First Number With Digit Sum k)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho các số nguyên $l,r,k$. Tìm số nguyên nhỏ nhất $x$ trong đoạn đóng $[l,r]$ có tổng các chữ số thập phân đúng bằng $k$; nếu không có thì in -1. Quy ước tổng chữ số của số 0 bằng 0. Duyệt x tăng dần; khi thấy đáp án, break khỏi vòng ngoài (thoát vòng chữ số thôi là chưa đủ).

Input

Một dòng chứa $l,r,k$ với $0\le l\le r\le100000$, $0\le k\le100$.

Output

In số nhỏ nhất thỏa mãn, hoặc -1.

Subtask

• 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$.

Ví dụ

Ví dụ 1

Input:

10 20 2

Output:

11

Giải thích:

Trong [10,20], số nhỏ nhất có tổng chữ số bằng 2 là 11.

Ví dụ 2

Input:

0 0 0

Output:

0

Giải thích:

Trong [0,0], số nhỏ nhất có tổng chữ số bằng 0 là 0.

Ví dụ 3

Input:

99 100 50

Output:

-1

Giải thích:

Trong [99,100], không có số nào có tổng chữ số bằng 50, nên in -1.