Мајката на Мендо решила да направи медена торта. За да го стори тоа и се потребни неколку јајца. Во шумската продавница се продаваат повеќе врсти на јајца (од различни производители: "Блиските кокошки од селото", "Кокошките од подалечното село", "Најубавите јајца од регионот" итн.). Јајцата се продаваат или во пакет од 6 или на парче (поединечно).

Ако за секоја врста на јајца ја знаеме цената на пакет од 6 јајца и цената за едно јајце, помогнете му на Мендо да го купи потребниот број на јајца за најевтина цена. Всушност, вие треба да пресметате колку најмалку пари може да потроши Мендо за купување на јајцата.

Мендо може да направи комбинација и да купи јајца од различни врсти со цел да постигне пониска цена. Некогаш е можеби поисплатливо да се купат 6 јајца на парче наместо пакет од 6. Всушност, пакет од 6 јајца е само група од 6 единични јајца, па еден пакет може да се замени со 6 единични јајца.

Може да се случи некогаш да е поисплатливо да се купат и повеќе од потребниот број на јајца, а цената да биде најниска. Тоа е исто така дозволено.

Внимавајте: Единствено е важно да се купат N јајца по најниска цена (не е важно од која врста се купените јајца). За да постигнеме најниска цена, можеме и да купиме јајца од различни врсти (на пример 6 јајца од една врста и 5 јајца од друга врста за вкупно 11 јајца).

Влез

Во првиот ред е даден цел број N (1 <= N <= 100) кој го ги означува бројот на јајца кои треба да се купат. Во вториот ред е даден цел број K (1 <= K <= 50), кој го означува бројот на врсти на јајца. Во секој од следните K редови се дадени по 2 цели броја Pi и Si (0 <= Pi, Si <= 1000), каде Pi ја означува цената на еден пакет од 6 јајца, додека Si ја означува цената на едно јајце (од таа врста).

Излез

На стандарден излез отпечатете ја минималната сума која треба да ја платите за да купите најмалку N јајца.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
17
1
12 3

излез
36

влез
7
2
10 3
12 2

излез
12

Објаснување за вториот пример: Треба да купиме 7 јајца и имаме избор од 2 врсти на јајца. Доколку купиме еден пакет од 6 јајца од првата врста (за цена 10), и едно единично јајце од втората врста (за цена 2), ќе купиме вкупно 7 јајца за цена од 10+2=12.