bzoj#P2385. [Ceoi2011]Hotel

[Ceoi2011]Hotel

题目描述

一个宾馆有 nn 个房间和 mm个预订,每个房间有住过之后的维护费用 cc 和最大入住人数 pp,每个预订有收入 vv 和人数 dd,大房间的维护费用不会比小房间的低,问你最多接受 oo 个预订的情况下的最大盈利。

输入格式

输出格式

样例输入

322
150 2
400 3
100 2
200 1
700 3

样例输出

400

数据规模与约定

对于 40%40\% 的数据,有 n,m100n,m\le 100

对于所有数据,保证 1n,m5×1051\le n,m\le 5\times 10^51omin(n,m)1\le o\le \min(n,m)1ci,pi,vj,dj1091\le c_i,p_i,v_j,d_j\le 10^9