You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

有 $m$ 位土拨鼠要来北辰OI俱乐部，你决定好好招待一下他们。

Description

超市里一共有 $n$ 袋瓜子，第 $i$ 袋瓜子里有 $c_i$ 个瓜子，第 $i$ 袋瓜子的美味度为 $d_i$。你希望买到的瓜子的个数能够平分给 $m$ 只土拨鼠，在此基础上，你又希望买到的瓜子的美味度最大。请你求出最大美味度。

Format

Input

第一行有两个正整数，$n$，$m$。后面 $n$ 行，每行两个正整数，分别表示 $c_i$ 和 $d_i$

Output

在买到瓜子的个数能够平分给 $m$ 只土拨鼠的基础上，能够买到的最大美味度。

Samples

5 4
1 2
2 3
3 4
4 5
5 6

16

1 4
1 999

0

Limitation

样例1：买第1，2，4，5袋瓜子可以得到12个瓜子，可以平分给4位土拨鼠，并且美味度为16。可以证明这是最大美味度。样例2：只有一袋都不买，得到0个瓜子，才能平分给4位土拨鼠，美味度为0。

• $1≤n≤1000$
• $1≤m≤100$
• $1≤c_i≤100$
• $1≤d_i≤1000$

1s, 1024KiB for each test case.