Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
 Time Limit: 2000MS Memory Limit: 131072K Total Submissions: 218 Accepted: 54

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 ≤ xiyin). The first of the remaining two lines contains n integers bi (0 ≤ bi ≤ 2000); the second contains m integers ci (0 ≤ ci2 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`

Hint

If two linear programs

minimize cTx

subject to

Axb,
x0

and

maximize bTy

subject to

ATyc,
y0

are both feasible, then x* and y*, the optimal solutions to them respectively, satisfy that cTx = bTy.

Source

[Submit]   [Go Back]   [Status]   [Discuss]