Lavrenty, a baker, is going to make several buns with stuffings and sell them.

Lavrenty has *n* grams of dough as well as *m* different stuffing types. The stuffing types are numerated from 1 to *m*. Lavrenty knows that he has *a*<sub class="lower-index">*i*</sub> grams left of the *i*-th stuffing. It takes exactly *b*<sub class="lower-index">*i*</sub> grams of stuffing *i* and *c*<sub class="lower-index">*i*</sub> grams of dough to cook a bun with the *i*-th stuffing. Such bun can be sold for *d*<sub class="lower-index">*i*</sub> tugriks.

Also he can make buns without stuffings. Each of such buns requires *c*<sub class="lower-index">0</sub> grams of dough and it can be sold for *d*<sub class="lower-index">0</sub> tugriks. So Lavrenty can cook any number of buns with different stuffings or without it unless he runs out of dough and the stuffings. Lavrenty throws away all excess material left after baking.

Find the maximum number of tugriks Lavrenty can earn.
The first line contains 4 integers *n*, *m*, *c*<sub class="lower-index">0</sub> and *d*<sub class="lower-index">0</sub> (1 ≤ *n* ≤ 1000, 1 ≤ *m* ≤ 10, 1 ≤ *c*<sub class="lower-index">0</sub>, *d*<sub class="lower-index">0</sub> ≤ 100). Each of the following *m* lines contains 4 integers. The *i*-th line contains numbers *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub>, *c*<sub class="lower-index">*i*</sub> and *d*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub>, *c*<sub class="lower-index">*i*</sub>, *d*<sub class="lower-index">*i*</sub> ≤ 100).
10 2 2 1
7 3 2 100
12 3 1 10
241
100 1 25 50
15 5 20 10
200
10 1 5 2
100 1 2 3
15
10 1 5 11
3 1 3 8
24
10 2 11 5
100 1 3 10
100 1 2 4
30
5 8 6 5
1 2 5 4
1 2 6 7
1 2 3 5
1 2 1 6
1 2 8 3
1 2 2 4
1 2 5 6
1 2 7 7
0
300 4 100 2
10 1 24 5
10 1 25 6
10 1 26 7
10 1 27 8
87
1 1 1 1
1 1 1 1
1
2 1 2 1
1 2 1 1
1
10 2 13 100
20 1 3 10
20 1 2 6
32
100 5 8 80
25 8 2 70
27 6 7 30
26 1 6 5
7 1 1 86
18 8 4 54
1670
150 8 3 46
39 4 10 25
31 17 8 70
37 2 13 1
29 17 17 59
54 20 5 39
53 14 10 23
50 12 16 41
8 2 6 61
2300
231 10 9 30
98 11 5 17
59 13 1 47
83 1 7 2
42 21 1 6
50 16 2 9
44 10 5 31
12 20 8 9
61 23 7 2
85 18 2 19
82 25 10 20
1065
345 10 5 45
1 23 14 55
51 26 15 11
65 4 16 36
81 14 13 25
8 9 13 60
43 4 7 59
85 11 14 35
82 13 5 49
85 28 15 3
51 21 18 53
3129
401 10 2 82
17 9 14 48
79 4 3 38
1 2 6 31
45 2 9 60
45 2 4 50
6 1 3 36
3 1 19 37
78 3 8 33
59 8 19 19
65 10 2 61
16400
777 10 23 20
50 90 86 69
33 90 59 73
79 26 35 31
57 48 97 4
5 10 48 87
35 99 33 34
7 32 54 35
56 25 10 38
5 3 89 76
13 33 91 66
734
990 10 7 20
38 82 14 69
5 66 51 5
11 26 91 11
29 12 73 96
93 82 48 59
19 15 5 50
15 36 6 63
16 57 94 90
45 3 57 72
61 41 47 18
2850
1000 10 51 56
2 62 82 65
37 90 87 97
11 94 47 95
49 24 97 24
33 38 40 31
27 15 17 66
91 80 34 71
60 93 42 94
9 35 73 68
93 65 83 58
1145
1000 10 1 53
63 1 1 58
58 1 2 28
100 1 1 25
61 1 1 90
96 2 2 50
19 2 1 90
7 2 1 30
90 1 2 5
34 2 1 12
3 2 1 96
55948
1000 10 1 65
77 1 1 36
74 1 1 41
96 1 1 38
48 1 1 35
1 1 1 54
42 1 1 67
26 1 1 23
43 1 1 89
82 1 1 7
45 1 1 63
66116
1000 10 1 87
100 1 1 38
100 1 1 45
100 1 1 73
100 1 1 89
100 1 1 38
100 1 1 13
100 1 1 93
100 1 1 89
100 1 1 71
100 1 1 29
88000
1000 10 1 7
100 1 1 89
100 1 1 38
100 1 1 13
100 1 1 93
100 1 1 89
100 1 1 38
100 1 1 45
100 1 1 73
100 1 1 71
100 1 1 29
57800
1000 10 1 100
100 1 1 100
100 1 1 100
100 1 1 100
100 1 1 100
100 1 1 100
100 1 1 100
100 1 1 100
100 1 1 100
100 1 1 100
100 1 1 100
100000
99 10 100 100
100 1 100 100
100 1 100 100
100 1 100 100
100 1 100 100
100 1 100 100
100 1 100 100
100 1 100 100
100 1 100 100
100 1 100 100
100 1 100 100
0
1000 10 100 75
100 97 100 95
100 64 100 78
100 82 100 35
100 51 100 64
100 67 100 25
100 79 100 33
100 65 100 85
100 99 100 78
100 53 100 74
100 87 100 73
786
999 10 5 100
100 1 10 100
100 1 10 100
100 1 10 100
100 1 10 100
100 1 10 100
100 1 10 100
100 1 10 100
100 1 10 100
100 1 10 100
100 1 10 100
19900
1000 10 50 100
7 1 80 100
5 1 37 100
9 1 25 100
7 1 17 100
6 1 10 100
5 1 15 100
6 1 13 100
2 1 14 100
4 1 17 100
3 1 32 100
4800
1000 10 1 1
1 2 1 97
1 2 1 95
1 2 1 99
1 2 1 98
1 2 1 93
1 2 1 91
1 2 1 90
1 2 1 94
1 2 1 92
1 2 1 99
1000
1 10 1 97
1 1 1 98
1 1 1 99
1 1 1 76
1 1 1 89
1 1 1 64
1 1 1 83
1 1 1 72
1 1 1 66
1 1 1 54
1 1 1 73
99
3 10 10 98
10 5 5 97
6 7 1 56
23 10 5 78
40 36 4 35
30 50 1 30
60 56 8 35
70 90 2 17
10 11 3 68
1 2 17 70
13 4 8 19
0
1000 1 23 76
74 22 14 5
3268
1000 2 95 56
58 54 66 61
61 14 67 65
713
1000 3 67 88
90 86 66 17
97 38 63 17
55 78 39 51
1232
1000 4 91 20
74 18 18 73
33 10 59 21
7 42 87 79
9 100 77 100
515
1000 5 63 52
6 98 18 77
17 34 3 73
59 6 35 7
61 16 85 64
73 62 40 11
804
1000 6 87 32
90 30 70 33
53 6 99 77
59 22 83 35
65 32 93 28
85 50 60 7
15 15 5 82
771
1000 7 59 64
22 62 70 89
37 78 43 29
11 86 83 63
17 48 1 92
97 38 80 55
15 3 89 42
87 80 62 35
1024
1000 8 31 96
6 94 70 93
73 2 39 33
63 50 31 91
21 64 9 56
61 26 100 51
67 39 21 50
79 4 2 71
100 9 18 86
4609
1000 9 55 28
38 74 22 49
9 74 83 85
63 66 79 19
25 32 17 20
73 62 20 47
19 27 53 58
71 80 94 7
56 69 62 98
49 7 65 76
831
1000 10 67 55
10 21 31 19
95 29 53 1
55 53 19 18
26 88 19 94
31 1 45 50
70 38 33 93
2 12 7 95
54 37 81 31
65 32 63 16
93 66 98 38
1161
1000 10 37 38
65 27 78 14
16 70 78 66
93 86 91 43
95 6 72 86
72 59 94 36
66 58 96 40
41 72 64 4
26 47 69 13
85 2 52 15
34 62 16 79
1156
1000 10 58 21
73 85 73 10
38 60 55 31
32 66 62 16
63 76 73 78
61 17 92 70
61 79 11 87
27 31 21 62
47 9 4 94
4 71 42 61
76 5 35 72
1823
12 2 100 1
100 1 9 10
100 1 4 4
12
1 1 1 10
100 100 1 100
100
10 3 5 1
100 1 3 7
100 1 2 5
1 1 1 10
32
10 3 5 1
100 1 3 7
100 1 2 5
1 1 1 10
32
1000 10 1 1
100 1 1 1
100 1 1 1
100 1 1 1
100 1 1 1
100 1 1 1
100 1 1 1
100 1 1 1
100 1 1 1
100 1 1 1
100 1 1 1
1000
10 2 100 1
4 4 5 7
6 2 3 4
12
8 2 10 10
5 5 5 15
50 5 4 8
16
8 2 10 10
5 5 5 15
50 5 4 8
16
4 1 2 4
10 1 3 7
8
4 1 2 4
10 1 3 7
8
10 2 5 1
100 1 2 5
100 1 3 8
26
1000 10 10 10
100 1 1 1
100 1 1 2
100 1 2 1
100 1 2 2
100 1 1 1
100 1 2 3
100 1 3 2
100 1 3 3
100 1 1 3
100 1 3 1
1400
10 3 5 1
100 1 3 7
100 1 2 5
1 1 1 10
32
n,m,c0,d0 = map(int,input().split())
l=[]
l.append([d0/c0,d0,c0,-1])
for i in range(m):
    a,b,c,d=map(int,input().split())
    l.append([d/c,d,c,a//b])
l.sort(reverse=True)
ans = 0
for i in range(m+1):
    if n==0:
        break
    e = n//l[i][2]
    if l[i][3]==-1:
        ans+=e*l[i][1]
        n-=e*l[i][2]
    else:
        ans+= min(e,l[i][3])*l[i][1]
        n-= min(e,l[i][3])*l[i][2]
        l[i][3]-= min(e,l[i][3])

        
print(ans)
