← 返回题目列表

AtCoder · awc0089_b

B. 连接管道

中文机器翻译题面 查看原题

分数: 333 分

问题陈述

高桥有 N 管道。的长度 i第管道是 A_i.

一些管道生锈了。如果 i第管子生锈了, B_i = 1;如果没有生锈的话 B_i = 0。由于生锈,生锈管道的有效可用长度减少到 \max(A_i - C, 0)。不锈管的有效长度为 A_i.

高桥自由选择 至少 1 个,最多 N 其中 N 管道(每个管道最多只能选择一次)并将它们连接成一条线以形成单个管道。如果只选择一根管子,则其有效长度直接成为成品管子的长度。如果选择两根或多根管道,则使用接头部件连接管道,因此成品管道的长度减少 每个连接点的 K 。

如果所选管道的数量为 M,有 M - 1 连接点,因此成品管的长度由以下公式给出:

(\text{sum of effective lengths of the } M \text{ selected pipes}) - (M - 1) \times K

高桥希望成品管的长度至少为 D。当最佳选择管道的组合和数量时,找到成品管道的最大可能长度。如果最大值至少为 D,输出该值;如果不可能达到的长度 D 以上无论选择,输出 -1.

约束

  • 1 \leq N \leq 10^5
  • 1 \leq D \leq 10^{14}
  • 1 \leq K \leq 10^9
  • 1 \leq C \leq 10^9
  • 1 \leq A_i \leq 10^9
  • B_i \in \{0, 1\}
  • 所有输入值均为整数。

输入

N D K C
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • 第一行包含管道数量 N,所需长度 D,每个连接点的长度减少 K,以及由于生锈而导致的长度减少 C,用空格分隔。
  • 从第 2 行到 (N + 1)第行,给出了每个管道的信息。
  • 的 (1 + i)第行包含长度 A_i 的 i第管道和 B_i (0 or 1) 表示是否生锈,以空格分隔。

输出

如果成品管的最大可能长度至少为 D,在单行上输出该最大值。如果不可能达到至少 D,输出 -1 在一行上。


示例输入 1

4 15 3 4
10 0
8 1
7 0
6 1

示例输出 1

15

示例输入 2

3 20 5 3
9 0
8 1
7 0

示例输出 2

-1

示例输入 3

8 40 4 5
12 0
11 1
20 0
9 1
15 0
7 0
14 1
10 0

示例输出 3

55

示例输入 4

15 90 7 10
30 0
25 1
18 0
40 1
12 1
9 0
27 0
14 1
33 0
21 1
16 0
45 1
8 1
19 0
24 1

示例输出 4

180

示例输入 5

1 1000000000 1000000000 1000000000
1000000000 0

示例输出 5

1000000000