#abc112b. [abc112_b]Time Limit Exceeded

[abc112_b]Time Limit Exceeded

题目描述

当X先生不在家时,他决定使用智能手表找到回家的最佳路线,参加ABC比赛。

智能手表为他找到了NN条回家的路线。

如果X先生选择第ii条路线,他将在时间tit_i内以花费cic_i的代价回家。

找到一条花费最小的同时不超过时间TT的路线。

约束条件

  • 输入中的所有值都是整数。
  • 1N1001 \leq N \leq 100
  • 1T10001 \leq T \leq 1000
  • 1ci10001 \leq c_i \leq 1000
  • 1ti10001 \leq t_i \leq 1000
  • 对于每对(ci,ti)(c_i, t_i),它们是不同的。

输入

输入格式如下:

N TN\ T

c1 t1c_1\ t_1

c2 t2c_2\ t_2

::

cN tNc_N\ t_N

输出

打印出一个花费最小且不超过时间TT的路线的代价。

如果没有一条花费不超过时间TT的路线,打印 TLE


示例输入 1

3 70
7 60
1 80
4 50

示例输出 1

4
  • 第一条路线花费77回到家。
  • 第二条路线的时间比T=70T = 70长。
  • 第三条路线花费44回到家。

因此,第三条路线的代价44是最小的。


示例输入 2

4 3
1 1000
2 4
3 1000
4 500

示例输出 2

TLE

没有一条路线的时间不超过T=3T = 3


示例输入 3

5 9
25 8
5 9
4 10
1000 1000
6 1

示例输出 3

5