도시 계획

어떤 행성에 우주 정거장이 건설되고 있다. 이 정거장에서는 $N$명이 일하게 되며, 이들이 살 곳이 필요하므로 정거장 주변에 도시를 짓는다. 정거장을 둘러싼 땅은 같은 크기의 정사각형 구획으로 나뉘고, 각 구획에는 최대 $K$층까지 올릴 수 있는 아파트 건물을 하나 지을 수 있다. 각 건물은 한 층에 정확히 한 세대씩 있으며, 모든 사람은 서로 다른 세대에 산다.

각 구획에는 $(x, y)$ 형태의 좌표가 매겨진다. 우주 정거장은 $(0, 0)$에 있고, 나머지 구획은 아래 그림과 같이 번호가 붙는다.

교통은 구획 사이의 도로로만 다닐 수 있으므로, 구획 $(x, y)$와 정거장 사이의 거리는 $|x| + |y| - 1$이다.

건물을 짓는 비용은 각 층을 짓는 비용의 합이다. 한 층을 짓는 비용은 그 층의 높이에만 의존하며, 건물의 위치와는 무관하다.

지어진 건물은 30년 동안 사용된다. 건물의 주민들은 정거장으로 출퇴근하는데, 30년 동안 한 주민을 정거장까지 오가게 하는 데 드는 교통 비용은 $T \cdot d$이다. 여기서 $d$는 그 주민이 사는 건물과 정거장 사이의 거리이다.

행성은 충분히 크고 건설되는 도시는 표면의 아주 작은 일부만 차지하므로, 행성 표면의 곡률은 고려하지 않아도 된다.

건물을 짓는 비용과 30년 동안 교통 시스템을 운영하는 비용을 합한 총 비용의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 정수 $N$ ($1 \le N \le 10^{12}$), $T$ ($1 \le T \le 500\,000$), $K$ ($1 \le K \le 20\,000$)가 공백으로 구분되어 주어진다.

이어지는 $K$개의 줄에는 각 층을 짓는 비용이 주어진다. $(i + 1)$번째 줄에는 그 아래 $i - 1$개 층이 이미 지어져 있다고 할 때 $i$번째 층을 짓는 비용 $c_i$ ($1 \le c_i \le 2 \cdot 10^{9}$)가 주어진다. 더 높은 층을 짓는 비용은 항상 더 크다. 즉, $c_1 < c_2 < \dots < c_K$이다.

도시를 건설하고 30년 동안 교통 시스템을 운영하는 데 드는 총 비용을 정수 하나로 출력한다. 답은 $8 \cdot 10^{18}$을 넘지 않으며 64비트 부호 있는 정수에 들어간다.