아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

기타줄

시간 제한2초메모리 제한128 MB

요약
여러 브랜드의 6개입 패키지 가격과 낱개 가격이 주어질 때, N개 이상의 기타 줄을 사는 최소 비용을 구한다.
난이도

쉬움10점 중 3점

유형
완전 탐색, 그리디, 수학
정답자
아직 제출이 없습니다

문제

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

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

입력

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

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

출력

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

힌트

추가 힌트는 없다.

예제6

  1. 예제 1

    입력
    4 2
12 3
15 4
    예상 출력
    12

  2. 예제 2

    입력
    10 3
20 8
40 7
60 4
    예상 출력
    36

  3. 예제 3

    입력
    15 1
100 40
    예상 출력
    300

  4. 예제 4

    입력
    17 1
12 3
    예상 출력
    36

  5. 예제 5

    입력
    7 2
10 3
12 2
    예상 출력
    12

  6. 예제 6

    입력
    9 16
21 25
77 23
23 88
95 43
96 19
59 36
80 13
51 24
15 8
25 61
21 22
3 9
68 68
67 100
83 98
96 57
    예상 출력
    6