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 x_i and y_i (1 ≤ x_i ≤ y_i ≤ n). The first of the remaining two lines contains n integers b_i (0 ≤ b_i ≤ 2000); the second contains m integers c_i (0 ≤ c_i ≤ 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 x_i through y_i (inclusive) sum to over c_i, 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 b_i’s as the weights.

Output

Output the highest possible total extra score. It is guaranteed to be bounded.

5 4
2 4
1 4
3 4
1 1
1 2
5 12 10 6
1 1 1 1 1

12

Hint

If two linear programs

minimize c^Tx

subject to

Ax ≥ b,
x ≥ 0

and

maximize b^Ty

subject to

A^Ty ≤ c,
y ≥ 0

are both feasible, then x* and y*, the optimal solutions to them respectively, satisfy that c^Tx = b^Ty.

Source

POJ Founder Monthly Contest – 2007.12.30, frkstyc