Tý có đa giác lồi \(N\) đỉnh, đỉnh i có trọng số \(w_i\). Chia đa giác thành các tam giác bằng cách vẽ các đường chéo không cắt nhau. Chi phí một tam giác \((i, j, k)\) là \(w_i + w_j + w_k\). Tìm tổng chi phí nhỏ nhất của phép chia.

#

Định dạng đầu vào

• Dòng 1: Số nguyên \(N\) (\(3 \le N \le 500\)).
• \(N\) dòng tiếp theo: mỗi dòng chứa tọa độ \((x_i, y_i)\) của đỉnh thứ i của đa giác lồi (\(|x_i|, |y_i| \le 10^4\)).

Định dạng đầu ra

• In ra tổng chu vi tối thiểu khi tam giác hóa đa giác lồi (làm tròn đến 4 chữ số thập phân).

Ví dụ

Input:

4
0 0
0 1
1 1
1 0

Output:

3.4142

Giải thích: Đường chéo nối \((0, 0)\) và \((1, 1)\) có độ dài \(\sqrt{2} \approx 1.4142\).

Ràng buộc & Subtasks