B - Connecting Pipes Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は N 本のパイプを持っています。i 番目のパイプの長さは A_i です。

一部のパイプは錆びています。i 番目のパイプが錆びている場合は B_i = 1、錆びていない場合は B_i = 0 で表されます。錆びたパイプは錆の影響で実際に使える長さ（有効長）が短くなり、\max(A_i - C, 0) になります。錆びていないパイプの有効長は A_i です。

高橋君はこれらの N 本のパイプから 1 本以上 N 本以下 を自由に選び（同じパイプを複数回選ぶことはできません）、一列につなぎ合わせて 1 本のパイプを作ります。1 本だけ選ぶ場合はそのパイプの有効長がそのまま完成品の長さになります。2 本以上選ぶ場合は、パイプ同士の接続にジョイント部品を使用するため、接続箇所 1 箇所あたり完成品の長さが K だけ短くなります。

選んだ本数を M とすると、接続箇所は M - 1 箇所あるため、完成するパイプの長さは次の式で求められます。

(\text{選んだ } M \text{ 本のパイプの有効長の合計}) - (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
  • 1 行目には、パイプの本数 N、必要な長さ D、接続 1 箇所あたりの長さの減少 K、錆による長さの減少 C が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各パイプの情報が与えられる。
  • 1 + i 行目では、i 番目のパイプの長さ A_i と、錆びているかを表す B_i（0 または 1）が、スペース区切りで与えられる。

出力

完成するパイプの長さの最大値が D 以上の場合は、その最大値を 1 行で出力せよ。D 以上にできない場合は -1 を 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

Score : 333 pts

Problem Statement

Takahashi has N pipes. The length of the i-th pipe is A_i.

Some pipes are rusted. If the i-th pipe is rusted, B_i = 1; if it is not rusted, B_i = 0. Due to rust, the effective usable length of a rusted pipe is reduced to \max(A_i - C, 0). The effective length of a non-rusted pipe is A_i.

Takahashi freely selects at least 1 and at most N of these N pipes (each pipe can be selected at most once) and connects them in a line to form a single pipe. If only one pipe is selected, its effective length directly becomes the length of the finished pipe. If two or more pipes are selected, joint parts are used to connect the pipes, so the finished pipe's length is reduced by K for each connection point.

If the number of selected pipes is M, there are M - 1 connection points, so the length of the finished pipe is given by the following formula:

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

Takahashi wants the length of the finished pipe to be at least D. When the combination and number of pipes are chosen optimally, find the maximum possible length of the finished pipe. If the maximum value is at least D, output that value; if it is impossible to achieve a length of D or more regardless of the selection, output -1.

Constraints

  • 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\}
  • All input values are integers.

Input

N D K C
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • The first line contains the number of pipes N, the required length D, the length reduction per connection point K, and the length reduction due to rust C, separated by spaces.
  • From the 2nd line to the (N + 1)-th line, the information for each pipe is given.
  • The (1 + i)-th line contains the length A_i of the i-th pipe and B_i (0 or 1) indicating whether it is rusted, separated by spaces.

Output

If the maximum possible length of the finished pipe is at least D, output that maximum value on a single line. If it is impossible to achieve a length of at least D, output -1 on a single line.

Sample Input 1

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

Sample Output 1

15

Sample Input 2

3 20 5 3
9 0
8 1
7 0

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

55

Sample Input 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

Sample Output 4

180

Sample Input 5

1 1000000000 1000000000 1000000000
1000000000 0

Sample Output 5

1000000000