题目描述

小z的假期开始了，他拿到了一份包含 $n$ 道题的题单，每道题都有一个完成所需的时间 $t_i$ 以及完成之后的得分 $w_i$

（注意：只有第一次通过才能获得分数）。

小z希望在今天花费不超过 $time$ 的时间，并且完成的题目数量不超过 $k$ 道的情况下，获得尽可能多的得分。请问小z今天最多能获得多少分？

数据范围

对于 $100$%的数据：$1≤n≤123,1≤k≤n,1≤time≤1440,1≤t_i,w_i≤500$。

输入格式

输入的第一行包含三个正整数，$n,k,time$，分别表示题目的数量，最多能完成的题目数量以及最多能花费的时间。

接下来的 $n$ 行，每行包含两个正整数 $t_i,w_i$，分别表示完成第 $i$ 道题所需的时间和得分。

输出格式

输出一个整数，表示小z在满足条件的情况下能获得的最大得分。

6 5 256
100 3 
100 4
200 6
50 1
50 2
100 1

9

6 3 1024
100 3 
100 4
200 6
50 1
50 2
100 1

13

提示