Background

Special for beginners, ^_^

Description

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

Format

Input

Output

Samples

322
150 2
400 3
100 2
200 1
700 3

400

Limitation

1s, 1024KiB for each test case.