Water Pipe Construction

The young goats often became thirsty while grazing and playing on a hill. They decided to build one water pipe to bring water from a river at distance D.

The goats obtained P pipes from a nearby village. The i-th pipe has length L_i and capacity C_i. D is between 7 and 100,000 inclusive, and P is between 1 and 350 inclusive. Both L_i and C_i are positive integers not greater than 2^23.

Each pipe may be used at most once. The selected pipes are connected in a line to make one water pipe. The length of the water pipe is the sum of the selected pipe lengths, and its capacity is the minimum capacity among the selected pipes.

Find the maximum possible capacity of a water pipe whose total length is exactly D.

The first line contains D and P.

Each of the next P lines contains the length L_i and capacity C_i of one pipe.

It is guaranteed that at least one subset of pipes has total length D.

Print the maximum possible capacity of a water pipe with total length exactly D.