만두 가게 사장 박승원

승원이는 오늘 가게에서 팔 만두를 빚으려고 한다. 만두는 밀가루로 만든 만두피에 만두 속을 넣어 빚는다.

가게에서 파는 만두는 모두 $m$종류이고, 지금 남은 밀가루는 $n$그램이다. 만두 종류에는 1번부터 $m$번까지 번호가 붙어 있다.

$i$번 만두에 넣는 만두 속은 $a_i$그램 남아 있고, 만두 한 개를 빚으려면 그 속이 $b_i$그램 필요하다. $i$번 만두의 만두피는 밀가루 $c_i$그램으로 만들고, 한 개를 $d_i$원에 판다.

스페셜 메뉴로 속 없이 만두피만 빚어 만드는 만두도 있다. 이 만두는 한 개에 밀가루 $c_0$그램이 들고, 한 개를 $d_0$원에 판다. 속을 쓰지 않으니 밀가루가 남아 있는 한 몇 개든 빚을 수 있다.

밀가루를 남겨도 되고, 만두를 한 개도 빚지 않아도 된다. 승원이가 빚은 만두의 판매 금액 합의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 $n$, $m$, $c_0$, $d_0$이 주어진다. ($1 \le n \le 1000$, $1 \le m \le 10$, $1 \le c_0, d_0 \le 100$)

다음 $m$개 줄의 $i$번째 줄에는 $a_i$, $b_i$, $c_i$, $d_i$가 주어진다. ($1 \le a_i, b_i, c_i, d_i \le 100$)

첫째 줄에 승원이가 빚은 만두의 판매 금액 합의 최댓값을 출력한다.

첫 번째 예제에서는 1번 만두 2개, 2번 만두 4개, 스페셜 만두 1개를 빚으면 된다. 두 번째 예제에서는 스페셜 만두 4개만 빚으면 된다.