【UNR #3】鸽子固定器 - 题目 - Universal Online Judge

为了固定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$ 个固定器的大小和牢固程度。

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

见样例数据下载。

子任务	分值	$n$ 的规模	$m$ 的规模	$d_{s}, d_{v}$ 的规模	$s_{i}, v_{i}$ 的规模	其他约定
1	5	$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}$	无
2	5	$1 \leq n \leq 1000$		$d_{s} = d_{v} = 2$
3	10	$1 \leq n \leq 2 \times 10^{5}$		$d_{s} = d_{v} = 1$
4	25			$d_{s} = d_{v} = 2$		$s_{i}, v_{i}$ 分别在某个范围内均匀随机生成
5	25			$d_{s} = 1, d_{v} = 2$		无
6	30			$1 \leq d_{s}, d_{v} \leq 2$		无

时间限制： $2 s$

空间限制： $512 MB$

Universal Online Judge