Burst Balloons

A row of balloons each shows a number. When you pop a balloon you score its number multiplied by the numbers on the balloons currently to its left and right; a missing neighbor at either end counts as 1. The popped balloon disappears, so the balloons on either side of it become neighbors.

Write max_score(balloons) that returns the highest total score you can get by popping every balloon in the best order.

Examples

max_score([2, 4, 3])     # returns 33
max_score([1, 5])        # returns 10
max_score([4, 2, 6, 1])  # returns 84
max_score([])            # returns 0

For [2, 4, 3], pop the 4 first for 2 * 4 * 3 = 24 points, then the 2 for 1 * 2 * 3 = 6, then the 3 for 1 * 3 * 1 = 3: 33 in total.

Constraints

• 0 <= len(balloons) <= 100
• 0 <= balloons[i] <= 100