分数: 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