Beaconator
Beaconator - Bring a Beacon to full power
EmeraldBoyGamer vừa hạ được \(10^{12}\) boss Wither và chế tạo được rất nhiều beacon. Cậu muốn đặt \(n\) beacon xuống căn cứ của mình, xếp chúng thành một hình chữ nhật đặc gồm các ô liền kề nhau.
Để kích hoạt được sức mạnh tối đa, beacon phải được đặt trên một kim tự tháp 4 tầng. Với một beacon đặt tại ô \((x, y)\), kim tự tháp bên dưới nó cần gồm 4 tầng, đánh số từ trên xuống từ 1 đến 4. Tầng thứ \(i\) là một hình vuông kích thước \((2i+1) \times (2i+1)\) có tâm tại \((x, y)\), nằm ngay dưới tầng \(i-1\) (tầng 1 nằm ngay dưới beacon). Như vậy, một beacon đứng riêng lẻ cần các tầng \(3\times3\), \(5\times5\), \(7\times7\) và \(9\times9\).

Hình 1: Cách đặt beacon trên các kim tự tháp (từ 1 tầng đến 4 tầng)
Tất cả \(n\) beacon được đặt ở cùng độ cao, mỗi beacon một ô, và các ô này tạo thành một hình chữ nhật \(a \times b\) (\(a \cdot b = n\)). Một trong các đặc điểm chính của beacon là các kim tự tháp của những beacon khác nhau được phép dùng chung block, tức là nếu một vị trí thuộc kim tự tháp của nhiều beacon thì chỉ cần đặt một block tại đó. Ví dụ, nếu đặt 2 beacon đứng cạnh nhau (\(1\times 2\)) thì các tầng tiếp theo là \(3\times 4\), \(5\times 6\), \(7\times 8\) và \(9\times 10\).

Hình 2: Cách đặt 6 beacon (\(2 \times 3\)) trên kim tự tháp 4 tầng
EmeraldBoyGamer chỉ dùng block lục bảo để xây kim tự tháp. Vì mỗi lần đi đổi đồ với dân làng cậu kiếm được không quá nhiều lục bảo, nên cậu cần tính toán kĩ lưỡng. Hãy giúp cậu biết số block cần dùng là ít nhất.
Dữ liệu
- Một dòng duy nhất chứa số nguyên \(N \ (1\le N \le 10^{12})\).
Kết quả
- Kết quả bài toán.
Chấm điểm
- Subtask 1 (70%): \(N \le 10^6\).
- Subtask 2 (30%): Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
1
output 164
Ví dụ 2
input
4
output
216
Giải thích
Ở ví dụ 2, bạn có thể đặt 4 đèn biển thành 1 hình vuông 2x2 để sử dụng ít vật liệu nhất.
Bạn có thể mở Minecraft và tự kiểm chứng.
Comments