1262. Last Stone Weight II

Given stone weights, repeatedly smash any two stones: if they are equal both are destroyed, otherwise the heavier one is replaced by the difference. Return the smallest possible weight of the final remaining stone (0 if none remains). The input is JSON {stones}.

Input: JSON {stones}.

Output: Integer — the smallest possible final weight.

Examples

Input: {"stones":[2,7,4,1,8,1]}
Output: 1
Explanation: An optimal sequence leaves a stone of weight 1.

Input: {"stones":[31,26,33,21,40]}
Output: 5
Explanation: The best achievable remainder.

Input: {"stones":[1]}
Output: 1
Explanation: One stone remains.

Constraints

• 1<=n<=30
• 1<=stones[i]<=100

Asked by