Maximizing Prize Packages

After the school sports meet, the school wants to reward as many students as possible with identical prize packages. Each prize package consists of (N) different items (for example, 5 pencils, 10 exercise books etc.). Some items are already available in the school storage from last year’s event, while additional items can be bought from a store. However, in the store, each type of item is available only in two kinds of packages: a large box or a small box, and they cannot be purchased separately. With a total budget of (M) yuan, determine the maximum number of complete prize packages that can be prepared.\n\nFor each of the (N) items, you are given: the required quantity per prize package, the quantity available from storage, and the details of the two types of boxes available in the store. In particular, for each item, you are provided with six integers: (r), (s), (a), (p_a), (b), (p_b) where (r) is the number of pieces required per prize, (s) is the number available in storage, and the store sells the item in two types of boxes: one containing (a) pieces for (p_a) yuan and the other containing (b) pieces for (p_b) yuan. You cannot buy individual pieces; you must purchase whole boxes.\n\nYour task is to compute the maximum number of prize packages that can be assembled by supplementing the storage with purchases from the store without exceeding the budget (M). For each item, if additional pieces are needed, you must choose a combination of small and large boxes to obtain at least the required additional pieces, while minimizing the cost.

inputFormat

The first line contains two integers (M) and (N) ((1 \leq M \leq 10^9), (1 \leq N \leq 100)), representing the total budget and the number of different items in a prize package.\n\nThen (N) lines follow, each containing six integers: (r), (s), (a), (p_a), (b), (p_b) (all positive), where:\n- (r) is the number of pieces required for that item per prize package,\n- (s) is the number of pieces available in storage,\n- (a) and (p_a) are the number of pieces and cost for the small box, and\n- (b) and (p_b) are the number of pieces and cost for the large box.

outputFormat

Output a single integer, the maximum number of complete prize packages that can be assembled within the budget (M).

sample

100 2
5 3 2 5 5 11
10 0 3 7 8 18

3