测试数据来自 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:提交了一年多也没通过审核。