题目描述

在出矿洞之前你采掘了许多铁矿石，现在你需要铁去造装备。 

一枚煤炭可以在熔炉内燃烧 y 秒融化至多x单位的铁矿石。 


而一枚暗物质可以在熔炉内燃烧  y22y 秒融化至多 2x 单位的铁矿石。 


同一时刻，熔炉只能燃烧一枚燃料。燃料均不可重复利用。


燃料燃烧完之前，你不可以获取熔炉中的矿物。 


你有一个神奇的卡特性的方法，可以将一枚煤炭升级成暗物质，这个方法至多只能使用一次。 


现在你有 1 个熔炉，n 枚煤炭和 m 单位铁矿石，问烧炼 m 单位铁矿石至少需要多长时间？

输入格式

第一行 两个正整数 n 和 m，n 表示有 n 枚煤炭，m 表示有 m 个单位的铁矿石 

接下来 n 行，每行两个正整数 xi 和 yi，代表第 i 枚煤炭可以在熔炉内燃烧 yi 秒融化单 xi 位的铁矿石  


1 ≤ n * m ≤ 1e6  


1 ≤ xi ≤1e9  


2 ≤ yi ≤1e9  


保证 ∑x ≥ m   y一定为偶数

输出格式

一个正整数，表示烧炼 m 单位铁矿石至少需要多长时间

5 28
6 8
5 4
6 10
5 2
6 4

14

提示

选择第 1, 2, 4, 5 煤炭，其中对第 1 枚煤炭使用魔法。 这样能融化 28 个单位的铁矿石，并且总燃烧时间最短，即 14