题目描述

经过一番努力，zyg终于见到了红魔馆的所有者——蕾米莉亚·斯卡雷特，众所周知，想要与她成为好朋友的方式是先打一架(bushi)。当然了，这样太过暴力，zyg还有其它的办法：蕾米莉亚是个长不大的孩子，即使她已经500岁了，但是心智仍然同小孩一般，所以zyg只需要买到足够的礼物，就可以和她成为好朋友了。

礼物总共有\(n\)种，且每种礼物，礼物直接送给蕾米可以获得蕾米的\(1\)点好感度，礼物还可以经过精美包装后再送给蕾米（包装也是要钱的），可以获得\(2\)点好感度，收集到足够好感度zyg就可以与蕾米做好朋友了。但zyg的钱包里的钱因为买fall guys等已经没了大半，所以他希望你能找到一个最便宜的方案来做蕾米的好朋友。

Format

输入数据

第一行共两个正整数\(n\)和\(m\)，\(n\)表示共有\(n\)种礼物，\(m\)为需要凑齐多少好感度才可以与蕾米作朋友。
接下来\(n\)行，每行两个正整数\(x\)和\(y\)，分别表示礼物购买的价钱\(x\)，及包装需要的价钱\(y\)。

输出数据

仅一个正整数，表示跟蕾米做朋友要花费的最少价钱。

Sample 1

Input

5 3
10 10
5 5
10 10
6 3
25 5

Output

14

Limitation

1s, 256MiB for each test case.

Hint

样例解释

直接买第二个礼物，并把第四个礼物包装好再送花费\(14\)元。

数据规模

对于前10%的数据，满足\(n \leq 100\)；
对于前40%的数据，满足\(n \leq 5000\)，\(m \leq 10000\)；
对于前40%的数据(8 个数据点)中的 4 个数据点满足\(x,y \leq 1000\)；
对于100%的数据，满足\(n \leq 100000\)，\(m \leq 200000\)；
对于100%的数据，满足\(x+y \leq 10^9\)。

Source

8月24日 夏日大礼包