P8680 [Lanqiao Cup 2019 NOI Qualifier B] Sum of Special Numbers

Xiaoming is very interested in numbers whose digits contain $2$, $0$, $1$, or $9$ (excluding leading $0$). From $1$ to $40$, such numbers include $1$, $2$, $9$, $10$ through $32$, $39$, and $40$, for a total of $28$ numbers, and their sum is $574$. Given $n$, find the sum of all such numbers from $1$ to $n$.

Input one line containing an integer $n$.

Output one line containing an integer, which is the sum of the numbers that satisfy the condition.

For $20\%$ of the test cases, $1 \le n \le 10$. For $50\%$ of the test cases, $1 \le n \le 100$. For $80\%$ of the test cases, $1 \le n \le 1000$. For all test cases, $1 \le n \le 10000$. Lanqiao Cup 2019 Provincial Contest B Group, Problem F. Translated by ChatGPT 5