This page is still under construction.

Parts of this page are still being built. What you see may change.

Interesting Number

Time limit2sMemory limit1024 MB

Summary
Given n up to 1000, find the smallest positive integer with digit sum n that is also divisible by n.
Level

Hard8 of 10

Topics
Dynamic programming, BFS, Number theory, Greedy
Solved
No attempts yet

Problem

For a given number nn, find the smallest positive integer whose digit sum is nn and which is divisible by nn.

Input

The input file contains a single integer nn (1≤n≤10001 \le n \le 1000).

Output

The output file must contain the required number. Leading zeros are not allowed.

Examples2

  1. Example 1

    Input
    1
    Expected output
    1

  2. Example 2

    Input
    10
    Expected output
    190