Một trạm không gian sẽ sử dụng \(N\) người. Thành phố dành cho họ được xây trên các lô đất vuông quanh trạm. Trạm nằm tại \((0,0)\); mỗi lô khác có tọa độ nguyên \((x,y)\). Trên mỗi lô có thể xây một tòa nhà không quá \(K\) tầng, mỗi tầng có đúng một căn hộ, và mỗi người sống trong một căn hộ riêng.

Do giao thông chỉ đi trên các đường giữa các lô, khoảng cách từ lô \((x,y)\) đến trạm là

Chi phí xây một tòa nhà bằng tổng chi phí xây từng tầng. Chi phí tầng chỉ phụ thuộc vào độ cao của tầng, không phụ thuộc vị trí. Trong \(30\) năm sử dụng, chi phí đưa một người đi lại giữa nhà và trạm là \(T\cdot d\), với \(d\) là khoảng cách từ tòa nhà đến trạm.

Hãy tìm tổng chi phí nhỏ nhất để xây đủ nhà ở và vận hành giao thông trong \(30\) năm.

Dữ liệu vào

Dòng đầu chứa \(N,T,K\). Mỗi dòng thứ \(i\) trong \(K\) dòng tiếp theo chứa \(c_i\), chi phí xây căn hộ ở tầng \(i\) khi các tầng thấp hơn đã được xây.

Dữ liệu ra

In một số nguyên: tổng chi phí nhỏ nhất.

Ràng buộc

• \(1\le N\le 10^{12}\).
• \(1\le T\le 500\,000\).
• \(1\le K\le 20\,000\).
• \(1\le c_i\le 2\,000\,000\,000\).
• \(c_1<c_2<\cdots<c_K\).
• Đáp án không vượt quá \(8\cdot 10^{18}\).

Ví dụ

17 5 4
100
107
114
121

1778