You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i-1] * nums[i] * nums[i+1] coins. If i-1 or i+1 goes out of bounds of the array, treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Example 1:

Input:  3 1 5 8
Output: 167

(3×1×5 + 3×5×8 + 1×3×8 + 1×8×1 = 15+120+24+8 = 167)

Example 2:

Input:  1 5
Output: 10

Constraints:

• n == nums.length
• 1 ≤ n ≤ 300
• 0 ≤ nums[i] ≤ 100

Input format: Space-separated integers.

Output format: Maximum coins.