Farmer John and his herd are playing frisbee. Bessie throws the frisbee down the field, but it's going straight to Mark the field hand on the other team! Mark has height H (1 <= H <= 1,000,000,000), but there are N cows on Bessie's team gathered around Mark (2 <= N <= 20). They can only catch the frisbee if they can stack up to be at least as high as Mark. Each of the N cows has a height, weight, and strength. A cow's strength indicates the maximum amount of total weight of the cows that can be stacked above her.

Given these constraints, Bessie wants to know if it is possible for her team to build a tall enough stack to catch the frisbee, and if so, what is the maximum safety factor of such a stack. The safety factor of a stack is the amount of weight that can be added to the top of the stack without exceeding any cow's strength.

Line 1: N and H.

Lines 2..1+N: Each describes a cow, giving its height, weight, and strength. All are positive integers at most 1 billion.

If a tall enough stack can be built, output the maximum achievable safety factor. Otherwise output "Mark is too tall" (without the quotes).

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > December > Gold