14855번 - 만두 가게 사장 박승원

문제

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

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

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

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

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

입력

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

다음 m개의 줄에는 a_i, b_i, c_i, d_i (1 ≤ a_i, b_i, c_i, d_i ≤ 100)가 주어진다.

출력

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

제한

힌트

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