工地搬砖生活
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\texttt{Bruce12138} 是计算机学院的一名学生,从小就喜欢码代码。他经过四年的学习,顺利从校园走向了社会并找到了一份工地搬砖工的工作。

在工地上,\texttt{Bruce12138} 认真学习如何处理砖块,怎样使用工具,取砖、放置、运输砖块。尽管他觉得比起写代码这份工作有点艰辛,但是他一直认为工地上是有趣的事情的。

有一天,包工头发现 \texttt{Bruce12138} 是一名计算机专业的学生,于是问他:“在我们这个工地里,你需要将 n 个砖块搬进体积为 V 的手推车。每个砖块 i 有两个固定属性:搬砖系数 g_i 和体积 v_i ,还有一个与此时手推车的剩余体积 V_{residue} 相关的动态属性搬砖舒适度c_i(c_i = g_i \times (V_{residue}-v_i)),搬砖舒适度是一个反映当前搬这块砖头的费力程度,搬砖舒适度越大,则搬这块砖越不费力。现在要求你合理安排搬砖顺序,将 n 块砖块全部搬进体积 V 尽可能小的手推车中,使得总搬砖舒适度 \sum_{i=1}^n c_i 至少达到给定的标准值 target 。你需要回答最小的手推车体积 V,答不出来就辞职吧。”

\texttt{Bruce12138} 虽然喜欢写代码,但却对这个数学问题完全一无所知。于是,他决定采取最后一个办法:使用特殊技能——校友召唤术,随机抽取一名校友来帮他解决问题。幸运地,你被抽取并接手了这个问题,请你帮他解决这个问题。

输入描述:

第一行,两个正整数 n(1\leq n \leq 10^5)target(1 \leq target \leq 10^9)

第二行至第 n+1行,每行两个正整数 g_i(1 \leq g_i \leq 10^2)v_i(1\leq v_i \leq 10^2),表示 n 个砖块的两个固定属性。

输出描述:

一行,表示答案。
示例1

输入

复制
3 100
1 1
2 2
3 3

输出

复制
21