题目描述

一个空间站建立在一个矩形平面上，坐标为 $(0,\ 0)$，这个空间站需要雇佣 $n$（$1\leq n\leq 10^{12}$）个员工。为了解决住宿问题，政府需要建设一个城市，城市包括一些最高不超过 $k$（$1\leq k\leq 2\times 10^4$）层的单元房。一个 $k$ 层的单元房占地为 $1\times 1$ 的单元格，可以住 $k$ 人，一个单元房在 $i$ 层的情况下增加一层需要花费 $c_{i+1}$（$1\leq c_i\leq 2\times 10^9$）元，满足 $c_1 < c_2 < \cdots < c_k$。城市中还需要建设交通网络，对于每个员工 $i$，交通建设花费为 $T\times d_i$（$1\leq T\leq 5\times 10^5$），其中 $d_i$ 表示该员工所住单元房与空间站的距离（注：$(x,\ y)$ 与空间站的距离为 $|x|+|y|$）。

请输出安排 $n$ 人住宿的最小花费。

输入格式

一行包含三个数 $N,\ K,\ T$。

输出格式

输出最少花费。

17 5 4
100
107
114
121

1778