|Online Judge||Problem Set||Authors||Online Contests||User|
Undergraduate Instruction Evaluation
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.
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 ≤
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 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
If two linear programs
Ax ≥ b,
ATy ≤ c,
are both feasible, then x* and y*, the optimal solutions to them respectively, satisfy that cTx = bTy.
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator