题目背景

海曙区“呦呦海贝”月赛即将开始，贝贝先在“海贝城堡”小游戏中热了热身。这一次，他需要合理安排守卫，守护城堡的每一段防线。

题目描述

城堡共有 $n$ 段防线，第 $i$ 段防线将受到 $a_i$ 只小怪的进攻。在这一段防线上，每名守卫最多可以击退 $k_i$ 只小怪。

贝贝共有 $s$ 名守卫，需要把他们分配到各段防线上。每名守卫只能被分配到一段防线，每段防线可以分配任意多名守卫，也可以不分配守卫。

如果第 $i$ 段防线上安排了 $x_i$ 名守卫，那么：

• 当 $a_i\leq x_i\times k_i$ 时，没有小怪能突破这一段防线；
• 当 $a_i>x_i\times k_i$ 时，会有 $a_i-x_i\times k_i$ 只小怪突破这一段防线。

请你帮助贝贝分配这 $s$ 名守卫，使突破防线的小怪总数尽可能少，并输出这个最小值。

输入格式

第一行包含两个整数 $n,s$，分别表示防线的段数和守卫的总人数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i,k_i$，分别表示进攻第 $i$ 段防线的小怪数量，以及每名守卫在这一段防线上最多可以击退的小怪数量。

输出格式

输出一个整数，表示最优分配方案下，突破防线的小怪总数。

样例 1

1 10
8 1

0

样例 1 解释

把所有守卫安排在唯一的一段防线上，可以击退全部 $8$ 只小怪，答案为 $0$。

样例 2

3 3
4 2
1 1
10 8

3

样例 2 解释

一种最优方案是第一段防线安排 $2$ 名守卫，第三段防线安排 $1$ 名守卫。三段防线分别有 $0,1,2$ 只小怪突破，总数为 $3$。

样例 3

2 1
5 100
8 6

7

样例 3 解释

把唯一的守卫安排在第二段防线上，可以击退 $6$ 只小怪，剩余 $5+2=7$ 只。虽然第一段防线的 $k_i$ 更大，但那里只有 $5$ 只小怪。

样例 4

2 2
9 5
6 6

4

样例 4 解释

在两段防线上各安排一名守卫，分别剩下 $4$ 只和 $0$ 只小怪，答案为 $4$。

样例 5

3 1
1000000000 1
1000000000 1
1000000000 1

2999999999

样例 5 解释

一共有 $3 \times 10^9$ 只小怪，唯一的守卫只能击退 $1$ 只，因此答案为 $2999999999$。

数据范围

对于所有测试数据，保证 $1\leq n\leq10^5$，$1\leq s,a_i,k_i\leq10^9$。

本题采用子任务计分。一个子任务内的全部测试点，以及它所依赖子任务的全部测试点均通过时，才能获得该子任务的分数。