小明的网络游戏

小明的网络游戏

测试数据来自 system/1328

背景

前些日子举行了OIBH杯NOIp2006模拟赛
第一题《容易的网络游戏》(P1238)的题目,小明(什么烂名)看了很不爽。

觉得每台电脑最多运行一个游戏的要求不合理,使此题太简单,于是就把题目改了……
(小明:“救命!……”)

描述

网络公司共推出n个游戏,每个游戏都有一段免费双倍经验时间,对于任何一款网络游戏,只要是在双倍经验的条件下,无论谁玩都可以在单位时间内轻松获得一个单位的经验值,小明(不是佳佳玩吗?小明你怎么……)决定只玩处于免费双倍经验开放时期的游戏。

我们假定,每台电脑最多只能有一人操作,一个人最多只能操作一台电脑;并且每款游戏最多只能在一台电脑上玩,每台电脑**在同一时间**最多运行一个游戏。我们忽略开始游戏和结束游戏时所消耗的时间。

现在小明想知道,假如他共有m台电脑,且一共叫来了(p-1)个同学(即加上他自己共p个人),那么他和他的同学们最多能得到多少单位的经验。

格式

输入格式

第一行有三个用空格隔开的整数n,m和p,它们表示的意义如题目描述。

以下n行,每行有两个用空格隔开的整数Xi,Yi(Xi<=Yi),表示从第Xi单位时间到第Yi单位时间(即1到2为2个单位时间)为第i款游戏开放双倍经验的时间。

1≤n≤100000
0≤Xi,Yi≤50000000
1≤p≤1000000
1≤m≤1000000

输出格式

输出一个整数,表示小明和他的同学们能获得的最大经验值。

样例1

样例输入1

3 2 1
0 5
2 6
8 9

样例输出1

9

限制

各个测试点2s

提示

数据比较BT……(WA了就改题 ^_^)
FAQ:那个比赛时前些日子举行的?
ANS:提交了一年多也没通过审核。

信息

ID
1428
难度
(无)
分类
数据结构 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者