【Castle Protecting】

题目背景

数据增强版

题目描述

Darkkingdom 侵占了 wisekingdom 的 St.Acerburg ,为了消灭敌人夺回城堡,St.Acerburg 的臣民决定向城堡投一种特殊的炸弹。这种炸弹的毁灭范围是一个矩形(即可以炸 1 个格子、或炸连续 2 个格子、或炸连续 4 个格子……可以控制范围,但必须是矩形)。St.Acerburg的城堡比较特殊,它只有两层,但很长。臣民们知道城堡上有 N 个敌人,并且知道他们在 a[i][0] 层楼的 a[i][1] 间房。现在他们手中有 K 枚炸弹,他们将消灭在城堡内的敌人,但是并不愿意破坏自己城堡的房屋。他们想知道最少要破坏多少间房才能消灭敌人。

输入格式

第一行:三个整数 N,K,B。分别为敌人的数目,炸弹的数目和城堡的长度。N,K<=1000,B<=15000000。
接下来 N 行,每行两个数,a[i][0],a[i][1],表示第 i 个敌人的位置。

输出格式

输出仅一行,即对最少需要破坏的房屋数目。

样例数据 1

输入

8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4

输出

10

备注

【样例说明】

2 个绿色部分分别是 2 颗炸弹覆盖范围,最少要炸掉 10 个房间。

【数据说明】
30% 的数据:N,K<=20;
60% 的数据:N,K<=200;
100% 的数据:N,K<=1000;
50% 的数据:B<=10000

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*