来硬的

题号：NC269435
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ $\hspace{15pt}$ $\hspace{15pt}$ $\hspace{15pt}$

$\hspace{15pt}$ 你厌倦了探索的日子，背包中堆满了铁矿石，准备放进熔炉烧炼。共有 $n$ 枚煤炭可供使用，第 $i$ 枚煤炭具有：
$\hspace{23pt}\bullet\,$ 可在熔炉中燃烧 $y_i$ 秒；
$\hspace{23pt}\bullet\,$ 最多融化 $x_i$ 单位铁矿石。

$\hspace{15pt}$ 你掌握一项魔法，至多对一枚煤炭施放，将其升级为暗物质燃料。若第 $i$ 枚煤炭被升级，则：
$\hspace{23pt}\bullet\,$ 燃烧时间变为 $\tfrac{y_i}{2}$ 秒；
$\hspace{23pt}\bullet\,$ 可融化的矿石数量变为 $2x_i$ 单位。

$\hspace{15pt}$ 熔炉同一时刻只允许燃烧一枚燃料；燃料耗尽之前，无法取出已融化的矿石。每枚燃料仅能使用一次。

$\hspace{15pt}$ 现在你拥有 $m$ 单位铁矿石，请计算最少需要多少秒才能全部烧炼完毕。

输入描述:

第一行输入两个整数 ——煤炭数量与铁矿石总量。接下来  行，第  行输入两个整数 ：
 ——可融化矿石数量；
  为偶数——燃烧时长。

数据保证 。

输出描述:

输出一个整数，表示烧炼完  单位铁矿石所需的最短时间。

示例1

输入

复制

输出

复制

说明

选择煤炭 ，并对煤炭  施放魔法：
  升级后燃烧  秒，融化  单位；
  燃烧  秒，融化  单位；
  燃烧  秒，融化  单位；
  燃烧  秒，融化  单位。

总计融化  单位铁矿石，耗时  秒，为最优方案。