Guitar Strings

N strings on Kangto's guitar have snapped. New strings can be bought either as packages of 6 strings or individually in any quantity.

For each brand, the package price and single-string price are given. Find the minimum cost needed to buy at least N guitar strings.

The first line contains the number of snapped strings N and the number of brands M. N is a positive integer at most 100, and M is a positive integer at most 50.

Each of the next M lines contains a brand's package price and single-string price, separated by a space. Every price is an integer between 0 and 1,000, inclusive.

Print the minimum cost needed to buy at least N guitar strings.

There is no additional hint.