C - Combination of Presents Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、青木君の誕生日プレゼントとして満足度が D 以上となるプレゼントを用意したいと考えています。

お店には N 種類の商品が並んでいます。 i 番目の商品（ 1 \leq i \leq N ）の満足度は A_i 、価格は C_i です。

高橋君は、次の 2 つの方法のいずれか一方を選んでプレゼントを用意します。

  • 方法 1: N 種類の商品の中から 1 つを選んで購入し、それを渡す。 i 番目の商品を選んだ場合、プレゼントの満足度は A_i 、価格は C_i となる。
  • 方法 2: N 種類の商品の中から異なる 2 つを選んで購入し、セットにして渡す。 i 番目の商品と j 番目の商品（ 1 \leq i < j \leq N ）を選んだ場合、プレゼントの満足度は A_i + A_j 、価格は C_i + C_j となる。

満足度が D 以上となるプレゼントを用意できる場合、そのようなプレゼントの価格の最小値を求めてください。どちらの方法を用いても満足度を D 以上にできない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D \leq 10^9
  • 1 \leq A_i \leq 10^9 （ 1 \leq i \leq N ）
  • 1 \leq C_i \leq 10^9 （ 1 \leq i \leq N ）
  • 入力はすべて整数である。

入力

N D
A_1 C_1
A_2 C_2
\vdots
A_N C_N
  • 1 行目には、商品の種類数 N と、必要な満足度の下限 D が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目（ 1 \leq i \leq N ）には、 i 番目の商品の満足度 A_i と価格 C_i がスペース区切りで与えられる。

出力

満足度が D 以上となるプレゼントの価格の最小値を 1 行で出力せよ。どちらの方法を用いても満足度を D 以上にできない場合は -1 を出力せよ。

入力例 1

4 10
4 300
7 500
6 200
3 100

出力例 1

500

入力例 2

3 100
20 1000
30 2000
40 3000

出力例 2

-1

入力例 3

10 25
8 700
14 1200
19 2500
5 300
11 600
20 5000
7 400
13 900
16 1500
3 200

出力例 3

1800

入力例 4

30 100
12 800
45 3200
60 7000
38 2500
72 9000
18 1200
55 4100
27 1800
66 7600
33 2200
81 15000
24 1600
49 3300
10 500
58 4300
41 2700
76 11000
29 1900
63 6500
35 2400
90 20000
21 1400
53 3900
47 3100
69 8200
15 900
57 4200
31 2100
74 9800
26 1700

出力例 4

7000

入力例 5

1 1000000000
1000000000 1000000000

出力例 5

1000000000

Score : 366 pts

Problem Statement

Takahashi wants to prepare a birthday present for Aoki with a satisfaction level of at least D.

There are N types of products available at the store. The i-th product (1 \leq i \leq N) has a satisfaction level of A_i and a price of C_i.

Takahashi will prepare the present by choosing one of the following two methods:

  • Method 1: Select 1 product from the N types of products, purchase it, and give it as a present. If the i-th product is selected, the satisfaction level of the present is A_i and the price is C_i.
  • Method 2: Select 2 different products from the N types of products, purchase them, and give them as a set. If the i-th product and the j-th product (1 \leq i < j \leq N) are selected, the satisfaction level of the present is A_i + A_j and the price is C_i + C_j.

If it is possible to prepare a present with a satisfaction level of at least D, find the minimum price of such a present. If it is not possible to achieve a satisfaction level of at least D using either method, output -1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D \leq 10^9
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers.

Input

N D
A_1 C_1
A_2 C_2
\vdots
A_N C_N
  • The first line contains the number of product types N and the required minimum satisfaction level D, separated by a space.
  • The i-th line (1 \leq i \leq N) of the following N lines contains the satisfaction level A_i and the price C_i of the i-th product, separated by a space.

Output

Output in one line the minimum price of a present with a satisfaction level of at least D. If it is not possible to achieve a satisfaction level of at least D using either method, output -1.

Sample Input 1

4 10
4 300
7 500
6 200
3 100

Sample Output 1

500

Sample Input 2

3 100
20 1000
30 2000
40 3000

Sample Output 2

-1

Sample Input 3

10 25
8 700
14 1200
19 2500
5 300
11 600
20 5000
7 400
13 900
16 1500
3 200

Sample Output 3

1800

Sample Input 4

30 100
12 800
45 3200
60 7000
38 2500
72 9000
18 1200
55 4100
27 1800
66 7600
33 2200
81 15000
24 1600
49 3300
10 500
58 4300
41 2700
76 11000
29 1900
63 6500
35 2400
90 20000
21 1400
53 3900
47 3100
69 8200
15 900
57 4200
31 2100
74 9800
26 1700

Sample Output 4

7000

Sample Input 5

1 1000000000
1000000000 1000000000

Sample Output 5

1000000000