시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 37 15 12 92.308%

문제

승원이는 오늘 가게에서 판매할 만두를 만드려고 한다. 만두는 만두피에 만두 속을 넣어서 예쁘게 빚어서 만드며, 만두피는 밀가루로 만든다.

가게에서 판매하는 만두는 총 m종류가 있으며, 현재 밀가루는 n그램 있다. 만두의 종류는 1번부터 m번까지 번호가 매겨져 있다.

i번 만두를 만들 수 있는 만두 속은 ai그램이 남아있으며, 만두 하나를 만들기 위해서 bi그램의 만두 속이 필요하다. i번 만두의 만두피는 ci그램의 밀가루로 만들어야 하며, 만두 하나당 판매 금액은 di원이다.

스페셜 메뉴로 만두 속 없이 만두 피만 가지고 만들 수 있는 만두도 있다. 이 만두는 하나를 만드는데 c0그램의 밀가루가 필요하고, 한 개당 d0원에 판매할 수 있다.

승원이가 만들 수 있는 만두 금액의 합의 최대값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n, m, c0, d0 (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10, 1 ≤ c0, d0 ≤ 100)이 주어진다.

다음 m개의 줄에는 ai, bi, ci, di (1 ≤ ai, bi, ci, di ≤ 100)가 주어진다.

출력

첫째 줄에 승원이가 만들 수 있는 만두 금액의 합의 최대값을 출력한다.

예제 입력 1

10 2 2 1
7 3 2 100
12 3 1 10

예제 출력 1

241

예제 입력 2

100 1 25 50
15 5 20 10

예제 출력 2

200

힌트

첫 번째 에제의 경우에는 1번 만두를 2개 만들고, 2번 만두를 4개 만들고, 스페셜 만두를 1개 만들면 되고, 두 번째 예제의 경우에는 스페셜 만두를 4개 만들면 된다.