Farmer John's Frisbee Stack

Farmer John and his herd are playing frisbee. Bessie throws the frisbee down the field, but it's headed straight for Mark, the field hand on the opposing team! Mark has a height \(H\) (\(1 \le H \le 10^9\)), and Bessie's team has \(N\) cows (\(2 \le N \le 20\)). The cows can catch the frisbee only if they can build a stack whose total height is at least \(H\).

Each cow is described by three integers: height, weight, and strength. A cow's strength is the maximum total weight of cows that can be stacked on top of her. In a valid stack, for every cow, the total weight of cows above her must not exceed her strength.

The safety factor of a stack is defined as the minimum additional weight that can be placed on top of the stack without causing any cow to exceed her strength. Bessie wants to know if it is possible to build a stack that is tall enough to catch the frisbee, and if so, what the maximum possible safety factor is.

If it is impossible to achieve a stack of height at least \(H\), output impossible.

Note: If there is a valid stack, the answer is the maximum safety factor among all valid stacking orders.

inputFormat

The first line of input contains two integers: \(H\) and \(N\), representing Mark's height and the number of cows on Bessie's team.

The following \(N\) lines each contain three integers describing a cow: its height, weight, and strength.

\(1 \le H \le 10^9\) and \(2 \le N \le 20\). The cows' attributes are positive integers.

outputFormat

If it is possible to build a stack with total height at least \(H\), output a single integer representing the maximum safety factor achievable. Otherwise, output impossible.

sample

10 2
5 3 10
6 4 5

2