Stone Game II

Hard

Alice and Bob play with piles of stones nums (pile i has nums[i] stones). Alice moves first with M = 1. On a turn a player takes all stones from the first X remaining piles where 1 <= X <= 2M, then M becomes max(M, X). Both play optimally to maximize their own stones. Return the maximum stones Alice can collect.

Example 1

Input:  nums = [2,7,9,4,4]
Output: 10

Example 2

Input:  nums = [1,2,3,4,5,100]
Output: 104

Constraints

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 10^4