背景

Yoki和Delayyy在玩选矩形的游戏...
 

描述

有一个由N个高度为1的长矩形叠成的图形,并且每一层所在区间都包含于下一层。请你从这个图形中选出K个不相交的矩形(高度可以不为1),使得它们覆盖的面积之和最大。

下图给出了一种由5个矩形叠置成的图形中,选3个矩形的方案。

 

 
   

输入格式

第一行二个非负整数n, k。
接下来n行, 每行二个整数l, r 表示该层长矩形的覆盖区间为[l, r]。
数据满足l不升,r不降。
 

输出格式

一行一个整数area表示最大面积。
 

样例输入

5 2
2 2
2 3
2 4
2 5
1 5

 

样例输出

12

 

数据范围与约定

n≤20000, k≤min(n, 100), 1≤l, r≤10^9
 

样例解释

一种最优方案如下: