#ABC112B. [ABC112B] Time Limit Exceeded

[ABC112B] Time Limit Exceeded

题目描述

外出している X さんは、ABC に参加するためにスマートウォッチで最適な帰宅経路を調べることにしました。

スマートウォッチであるあなたは、N N 個の帰宅経路を見つけました。

X さんが i i 番目の経路を使う場合、コスト ci c_i かけて時間 ti t_i で帰宅できます。

時間 T T 以内に帰宅できる経路のうち、コストが最小となる経路のコストを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N T T c1 c_1 t1 t_1 c2 c_2 t2 t_2 : : cN c_N tN t_N

输出格式

時間 T T 以内に帰宅できる経路のうち、コストが最小となる経路のコストを出力せよ。

ただし、どの経路を使っても時間 T T 以内に帰宅できない場合、TLE と出力せよ。

题目大意

X 先生出门在外时,他决定使用智能手表搜索回家的最佳路线,以参加 ABC。

您,智能手表,已经找到到他家的 NN 条路线。

如果 X 先生使用这些路线中的第 ii 条,他将在时间 tit_i 到家,费用为 cic_i

找到不超过时间 TT 的路线的最小成本。

3 70
7 60
1 80
4 50
4
4 3
1 1000
2 4
3 1000
4 500
TLE
5 9
25 8
5 9
4 10
1000 1000
6 1
5

提示

制約

  • 入力はすべて整数である
  • 1  N  100 1\ \leq\ N\ \leq\ 100
  • 1  T  1000 1\ \leq\ T\ \leq\ 1000
  • 1  ci  1000 1\ \leq\ c_i\ \leq\ 1000
  • 1  ti  1000 1\ \leq\ t_i\ \leq\ 1000
  • (ci, ti) (c_i,\ t_i) の組は異なる

Sample Explanation 1

- 1 1 番目の経路を使うと、コスト 7 7 で帰宅できます - 2 2 番目の経路では時間 T = 70 T\ =\ 70 以内に帰宅できません - 3 3 番目の経路を使うと、コスト 4 4 で帰宅できます 従って、3 3 番目の経路を使ったときのコスト 4 4 が最小です。

Sample Explanation 2

どの経路を使っても時間 T = 3 T\ =\ 3 以内に帰宅できません。