You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the two heaviest stones and smash them together. Suppose the heaviest two stones have weights x and y with x ≤ y. The result: if x == y, both destroyed; if x != y, stone of weight y-x survives.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Example 1:

Input:  2 7 4 1 8 1
Output: 1

Example 2:

Input:  1
Output: 1

Constraints:

• 1 ≤ stones.length ≤ 30
• 1 ≤ stones[i] ≤ 1000

Input format: Space-separated integers.

Output format: Weight of last stone, or 0.