You have balloons with numbers. Bursting balloon i earns nums[i-1] × nums[i] × nums[i+1] coins (a missing neighbour counts as 1). After a burst its neighbours become adjacent. Find the maximum coins you can collect by bursting all balloons.
Input: one line of space-separated integers. Output: the maximum coins.
Your program reads from stdin and prints to stdout.
Example 1
Input: 3 1 5 8
Output: 167
Hints
You have balloons with numbers. Bursting balloon i earns nums[i-1] × nums[i] × nums[i+1] coins (a missing neighbour counts as 1). After a burst its neighbours become adjacent. Find the maximum coins you can collect by bursting all balloons.
Input: one line of space-separated integers. Output: the maximum coins.
Your program reads from stdin and prints to stdout.
Example 1
Input: 3 1 5 8
Output: 167
Hints