该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在劳动节期间，育华学校组织学生进行校园清洁活动。学校有 $n$ 个清洁区域（$1\leq n\leq 1000$），每个清洁区域有不同的清洁难度系数 $d_i$（$1\leq d_i\leq 100$），以及完成该区域清洁所需的最少学生数量 $s_i$（$1\leq s_i\leq 10$）。

学校一共有 $m$ 名学生（$1\leq m\leq 1000$）参与清洁活动，现在需要合理分配学生到各个清洁区域，使得被清洁的区域的难度系数总和最大。每个学生只能分配到一个清洁区域，且每个清洁区域只有分配到足够数量的学生才能进行清洁。

请你编写一个程序，计算出在满足条件下，被清洁区域的难度系数总和的最大值。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示清洁区域的数量和参与活动的学生总数。 接下来 $n$ 行，每行包含两个整数 $d_i$ 和 $s_i$，分别表示第 $i$ 个清洁区域的难度系数和完成该区域清洁所需的最少学生数量。

输出格式

输出一个整数，表示在满足条件下，被清洁区域的难度系数总和的最大值。

样例

• 输入

3 5
3 2
4 3
5 4

• 输出

7