题目描述

原题已经指路了，是 ABC333C，当然本题进行了数据范围的增大。

定义一个概念“纯1数”：即一个数字都是由 $1$ 组成，比如 $1,11,111,1111...$

现在任选 $3$ 个纯1数 $a,b,c$，求出三数之和：$s=a+b+c$，对去重之后的所有 $s$ 进行排序，求出其中第 $n$ 个数是多少？

输入格式

$1$ 个正整数 $n$，表示要求的去重后的第 $n$ 大的纯1数之和

输出格式

$1$ 个正整数，如题目所求

输入输出样例

5

113

样例 $\tt \#1$说明

前几个去重后的 $s$ 结果为：$3(1+1+1),13(1+1+11),23(1+11+11),33(11+11+11),113(1+1+111)...$

其中第 $5$ 大的是 $113$

19

2333

数据范围

$30\%:n\le 300$

$100\%:1\le n\le 5\times10^5$