Blend to threshold: hints, no solution

A relief depot holds supplies, each with a strength value. Every supply must reach at least the strength threshold before it can be shipped. The only operation is a blend: take the two weakest supplies, with strengths x and y where x is not larger than y, and replace them with one new supply of strength x + 2y. If several supplies share the weakest strength, any of them may be used.

Repeat blends until every supply has strength of at least threshold, and return how many blends were needed. If all supplies already qualify, the answer is 0. If only one supply remains and it is still below the threshold, no blend is possible, so return -1.

Examples

Input

supplies = [1, 2, 4], threshold = 10

Output

2

Note

Blend 1 and 2 into 5, then blend 4 and 5 into 14, which reaches the threshold.

Input

supplies = [5, 6], threshold = 5

Output

0

Note

Both supplies already reach the threshold.

Constraints

• 1 <= number of supplies <= 100000
• 1 <= supplies[i] <= 1000000
• 1 <= threshold <= 1000000000

Hint 1: a nudge

After one blend, which supplies are the weakest now? Does the new supply ever end up weaker than the ones you used?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing