Shennong asked Chisongzi for advice on the way of longevity. Chisongzi taught Shennong how to choose fairy grass and prolong life. Chisongzi took Shennong to Shennongjia and told him: "there are fairy grasses on the mountain. It takes some time to pick each grass, and each grass also has its own use value. There are also three rare grasses on the mountain, which are used independently and have strange poison. However, any two rare grasses used at the same time can be equivalent to a fairy grass, and its use value is the product of the value of two rare grasses, but each rare grass can not be reused. I will give you a period of time. During this period, you should pick some grasses as much as possible to maximize the total use value of the grasses.
Shennong acted immediately, tasted all kinds of grass and fulfilled his mission. Do you know how Shennong accomplished this task?
The input has multiple cases (no more than 100) of test data.
The first line of each test cases is two positive integers T（1 ≤ T ≤ 1000） and M（1 ≤ M ≤ 100）, representing the time used to collect grass and the number of fairy grass on Shennongjia. Next, there are M lines. Each line contains two positive integers t and v (1 ≤ t, v ≤ 100), representing the time of picking the fairy grass and the value of the fairy grass respectively. The last three lines are the picking time a (1 ≤ a ≤ 100) and use value b (- 100 ≤ b < 0) of three rare grasses.
The end of input will be represented by a line of test case where T and M are equal to 0. This test case should not be processed.
Each test case outputs a line, which is an integer, indicating the maximum total use value of fairy grass that can be collected in T time.
70 3
71 100
68 3
1 2
1 -2
1 -3
1 -4
0 015