提示: 欢迎访问OurACM平台。
Problem 2101 大三的美好时光

Accept: 66    Submit: 367
Time Limit: 3000 mSec    Memory Limit : 32768 KB

Problem Description

依稀记得自己踏入福大时学长学姐的甜美笑脸,可是一转眼的功夫自己就是大三的学长了。时间匆匆而过也就算了,bluesun痛苦的是,到大三了校选课还没有修满,再加上院选和必修课,bluesun的大三注定是异常辛苦的一年。

Bluesun总是喜欢把要做的事情在最短的时间里做完,所以他决定在必修课必选之外,选择一种使自己可以得到最多学分的方案(不管是院选的学分还是校选的,bluesun只要求学分尽量多)。

Input

数据有多组,请处理到文件结尾。

每组数据的第一行为n(n表示有n门课程可供选择)接下来n行,每行4个整数,t 、l、 r和 v,如果t==0,则表示这门课程是必修课,否则为院选课或者是校选课,l和r表示该门课程占用的时间段为[l,r],v表示该门课程占几个学分。

输入数据均为整数,并且保证必修课的时间不会有交叉,1<=n<=100000,0<=v<=10000,1<=l<=r<=2^30。

Output

每组测试输出一个整数,每个整数占1行,表示bluesun这个学期最多可以修多少个学分。

Sample Input

1 1 1 1 2

Sample Output

2

Source

FOJ有奖月赛-2012年11月

Submit  Back  Status  Discuss