UOJ Logo Universal Online Judge

UOJ

#386. 【UNR #3】鸽子固定器

统计

为了固定S**p*鸽鸽,whx和zzt来到鸽具商店选购鸽子固定器。

鸽具商店有 $n$ 个不同大小的固定器,现在可以选择至多 $m$ 个来固定S**p*鸽鸽。每个固定器有大小 $s_i$ 和牢固程度 $v_i$。

如果他们选购的固定器大小不一或是不牢固,固定S**p*鸽鸽的时候肯定会很头疼,所以定义选择的物品总牢固程度和的 $d_v$ 次方减大小极差的 $d_s$ 次方为这个方案的价值,求不同选购方案中,价值的最大值。

鸽子

输入格式

第一行四个正整数 $n,m,d_s,d_v$。

接下来 $n$ 行,每行两个正整数 $s_i,v_i$,表示第 $i$ 个固定器的大小和牢固程度。

输出格式

输出一行,包含一个整数,表示价值的最大值。

样例一

input

3 2 1 1
4 2
1 3
5 10

output

11

样例二

input

3 2 2 2
4 2
1 3
5 10

output

153

样例三

见样例数据下载。

限制与约定

子任务 分值 $n$ 的规模 $m$ 的规模 $d_s,d_v$ 的规模 $s_i,v_i$ 的规模 其他约定
15$1 \leq n \leq 10$$1 \leq m \leq \min(50, n)$$d_s = d_v = 2$$1 \leq s_i,v_i \leq 10^7$
25$1 \leq n \leq 1000$
310$1 \leq n \leq 2 \times 10^5$$d_s=d_v=1$
425$d_s=d_v=2$$s_i,v_i$分别在某个范围内均匀随机生成
525$d_s=1,d_v=2$
630$1 \leq d_s,d_v \leq 2$

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载