Description
Inspectors from the Ministry of Education are coming to frkstyc’s university to evaluate its undergraduate instruction. Although the university is among the best ones in the country, the dean office rules that there is still room for improvement. Now they have produced a list of points of possible improvement, such as trimming the trees and lawns on the campus and lowering the rate of late arrivals at classes.
Improvement is good, whereas overdoing that is not. Nicely tidied dormitories are certainly eyeball-catching. But if they gets extravagantly decorated, they will be dimmed solely as evidence of affectation for sure. With the evaluation program in hand, the dean office has to decide how much effort to spend on each point of improvement so that the university will score in extra as high as possible without the inspectors perceiving any pretence.
Input
The input consists of a single test case. The first line contains two integers m and n (1 ≤ m ≤ 4000, 1 ≤ n ≤ 200). The next m lines each contain a pair of integers xi and yi (1 ≤ xi ≤ yi ≤ n). The first of the remaining two lines contains n integers bi (0 ≤ bi ≤ 2000); the second contains m integers ci (0 ≤ ci ≤ 2 000 000).
The input is interpreted as follows. The dean office has listed n points to improve, from which arise m sources of possible recognizable affectation. Since the points are appropriately grouped into categories, these sources of troubles can be describe economically: for each i = 1, 2, …, m, if the score increases from points numbered xi through yi (inclusive) sum to over ci, some inspector will believe what he/she has seen is deliberate and unnatural. The total extra score is calculated as the weighted sum of score increase in each point with the bi’s as the weights.
Output
Output the highest possible total extra score. It is guaranteed to be bounded.
Sample Input
5 4
2 4
1 4
3 4
1 1
1 2
5 12 10 6
1 1 1 1 1
Sample Output
12
