在藍(lán)橋王國(guó)中，有 n 名士兵，這些士兵需要接受一系列特殊的訓(xùn)練，以提升他們的戰(zhàn)斗技能。對(duì)于第 i 名士兵來說，進(jìn)行一次訓(xùn)練所需的成本為 pi 枚金幣，而要想成為頂尖戰(zhàn)士，他至少需要進(jìn)行 ci 次訓(xùn)練。

為了確保訓(xùn)練的高效性，王國(guó)推出了一種組團(tuán)訓(xùn)練的方案。該方案包含每位士兵所需的一次訓(xùn)練，且總共只需支付 S 枚金幣（組團(tuán)訓(xùn)練方案可以多次購(gòu)買，即士兵可以進(jìn)行多次組團(tuán)訓(xùn)練）。

作為訓(xùn)練指揮官，請(qǐng)你計(jì)算出最少需要花費(fèi)多少金幣，才能使得所有的士兵都成為頂尖戰(zhàn)士？

3 6
5 2
2 4
3 2

16

【樣例說明】

花費(fèi)金幣最少的訓(xùn)練方式為：進(jìn)行 2 次組團(tuán)訓(xùn)練，花費(fèi) 2 × 6 = 12 枚金幣，此時(shí)士兵 1, 3 已成為頂尖戰(zhàn)士；再花費(fèi) 4 枚金幣，讓士兵 2 進(jìn)行兩次訓(xùn)練，成為頂尖戰(zhàn)士?？偦ㄙM(fèi)為 12 + 4 = 16。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 40% 的評(píng)測(cè)用例，1 ≤ n ≤ 10³，1 ≤ p_i, c_i ≤ 105，1 ≤ S ≤ 10⁷。

對(duì)于所有評(píng)測(cè)用例，1 ≤ n ≤ 10⁵，1 ≤ p_i, c_i ≤ 106，1 ≤ S ≤ 1010。