题目描述

一个宾馆有 $n$ 个房间和 $m$个预订，每个房间有住过之后的维护费用 $c$ 和最大入住人数 $p$，每个预订有收入 $v$ 和人数 $d$，大房间的维护费用不会比小房间的低，问你最多接受 $o$ 个预订的情况下的最大盈利。

输入格式

输出格式

样例输入

322
150 2
400 3
100 2
200 1
700 3

样例输出

400

数据规模与约定

对于 $40\%$ 的数据，有 $n,m\le 100$。

对于所有数据，保证 $1\le n,m\le 5\times 10^5$，$1\le o\le \min(n,m)$，$1\le c_i,p_i,v_j,d_j\le 10^9$。