You are given n balloons, each painted with a number.
Burst balloon i to gain nums[left] * nums[i] * nums[right] coins where left and right are adjacent still-unburst balloons. Return the maximum coins possible.
Examples
Input: nums = [3,1,5,8] Output: 167
Input: nums = [1,5] Output: 10
Constraints
- 1 <= nums.length <= 300
- 0 <= nums[i] <= 100