「eJOI2021」河畔

ID: 4498

传统题

3000ms

1024MiB

尝试: 8

已通过: 1

难度: 10

上传者:

2300770227

标签>

贪心

最优化

二分答案

题目描述

普洛耶什蒂（Ploiești）市市长在普拉霍瓦河（Prahova River）畔种了一排 $N$ 棵不同品种的观赏性灌木。每棵灌木初始高度为 $h_i$ 。根据种植的土壤条件和天气状态，第 $i$ 棵灌木每天生长的高度为 $d_i$ 。

每天，市政厅的园丁都会通过用剪刀修剪灌木来调整这些灌木的高度。然而，园丁被剪刀的质量所限制。因此对于一次修剪，如果这棵灌木至少 $x$ 厘米高，那么园丁可以恰好从这棵灌木剪下 $x$ 厘米的高度（注意剪完之后灌木的高度可以为 $0$ ）。为了不会很累，园丁一天可以进行最多 $k$ 次修剪。在一天里园丁可以对同一灌木修剪多次。

市长会在 $M$ 天后组织一次艺术活动，他希望知道在 $M$ 天后最高的灌木最矮可能是多高。

注意：对于每天，树先生长，然后进行修剪。

输入格式

第一行四个整数 $N, M, k, x$ 。

接下来 $N$ 行，每行两个整数 $h_i, d_i$ 。

输出格式

输出一个非负整数，表示 $M$ 天后最高的灌木最矮可能的高度。

样例

输入

输出

园丁会修剪 $3$ 天，每天修剪 $4$ 次。每次修剪可以从一棵树上剪掉 $3$ 厘米。下表展示了最优修剪策略。

日期	树木	操作
1		$2 \stackrel{+5}{\rightarrow} 7 \stackrel{-3}{\rightarrow} 4$
	2	$3 \stackrel{+2}{\rightarrow} 5$
	3	$0 \stackrel{+4}{\rightarrow} 4$
	4	$2 \stackrel{+8}{\rightarrow} 10 \stackrel{-3}{\rightarrow} 7 \stackrel{-3}{\rightarrow} 4 \stackrel{-3}{\rightarrow} 1$
2	1	$4 \stackrel{+5}{\rightarrow} 9 \stackrel{-3}{\rightarrow} 6 \stackrel{-3}{\rightarrow} 3$
	2	$5 \stackrel{+2}{\rightarrow} 7$
	3	$4 \stackrel{+4}{\rightarrow} 8$
	4	$1 \stackrel{+8}{\rightarrow} 9 \stackrel{-3}{\rightarrow} 6 \stackrel{-3}{\rightarrow} 3$
3	1	$3 \stackrel{+5}{\rightarrow} 8$
	2	$7 \stackrel{+2}{\rightarrow} 9 \stackrel{-3}{\rightarrow} 6$
	3	$8 \stackrel{+4}{\rightarrow} 12 \stackrel{-3}{\rightarrow} 9 \stackrel{-3}{\rightarrow} 6$
	4	$3 \stackrel{+8}{\rightarrow} 11 \stackrel{-3}{\rightarrow} 8$

数据范围与提示

$1 \le k \le 1000$
$1 \le x \le 10^4$
$0 \le h_i \le 10^4$
$0 \le d_i \le 10^4$

#	分值	限制
1	8	$N \le 100, M=1, k=1, x=1, h_i \ge 1, d_i=0$
2	22	$1 \le N,M \le 500$
3	43	$1 \le N,M \le 5000$
4	27	$1 \le N,M \le 10^4$

#L3588. 「eJOI2021」河畔

题目描述

输入格式

输出格式

样例

数据范围与提示

还没有账户？

登录