Cho một mảng các số nguyên dương, hãy xem xét tất cả các cây nhị phân sao cho:

Mỗi nút có \(0\) hoặc \(2\) nút con; Các giá trị của \(arr\) tương ứng với các giá trị của mỗi lá trong một lần duyệt cây theo thứ tự. Giá trị của mỗi nút không phải lá tương ứng bằng tích của giá trị lá lớn nhất trong cây con trái và phải của nó. Trong số tất cả các cây nhị phân có thể được xem xét, trả về tổng giá trị nhỏ nhất có thể có của mỗi nút không phải lá. Nó được đảm bảo rằng tổng này phù hợp với số nguyên 32 bit.

Một nút là một lá khi và chỉ nếu nó không có con nào.

Ràng buộc:

• \(2 \le arr.length \le 40\)
• \(1 \le arr[i] \le 15\)

Input

6 2 4

Output

32

Giải thích

Đây là hai cây có thể được hiển thị.
Nút đầu tiên có tổng nút không phải lá là 36 và nút thứ hai có tổng nút không phải lá là 32.

Input 2

4 11

Output 2

44