기타줄

강토의 기타에서 N개의 줄이 끊어졌다. 새 줄은 6개가 들어 있는 패키지로 살 수도 있고, 필요한 만큼 낱개로 살 수도 있다.

브랜드마다 패키지 가격과 낱개 가격이 주어진다. 적어도 N개의 기타줄을 사기 위해 필요한 최소 비용을 구하라.

첫째 줄에 끊어진 기타줄의 수 N과 브랜드의 수 M이 주어진다. N은 100 이하의 자연수이고, M은 50 이하의 자연수이다.

둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개 가격이 공백으로 구분되어 주어진다. 모든 가격은 0 이상 1,000 이하의 정수이다.

기타줄을 적어도 N개 사기 위해 필요한 최소 비용을 첫째 줄에 출력한다.

추가 힌트는 없다.