Old Wine Into New Bottles

Wine bottles are never filled completely: a little air must be left in the neck so the wine can expand and contract with temperature. If too little air is left, the wine may expand and push out the cork; if too much air is left, the wine may spoil. Because of this, every bottle has a minimum and a maximum capacity.

You are given a quantity of wine and a selection of bottle sizes. You want to fill each bottle you use to somewhere between its minimum and maximum capacity while bottling as much wine as possible. Decide how many bottles of each size to use.

The first line contains two integers: the amount of wine to be bottled (in litres, between 0 and 1,000,000) and the number of bottle sizes (between 1 and 100).

Each of the following lines describes one bottle size by its minimum and maximum capacity in millilitres. The maximum capacity is between 325 and 4,500 inclusive. The minimum capacity is between 95% and 99% of the maximum capacity, inclusive. An unlimited number of bottles of each size is available.

The wine amount is given in litres, while bottle capacities and the answer are in millilitres (1 litre = 1,000 millilitres).

Print a single integer: the amount of wine, in millilitres, that cannot be bottled.