PRA3: Playlist // Advanced

You have a playlist consisting of $n$ songs. The $i^{th}$ song is characterized by two numbers $t_i$ and $b_i$ — its length and beauty respectively. The pleasure of listening to a set of songs is equal to the total length of the songs in the set multiplied by the minimum beauty among them. For example, the pleasure of listening to a set of $3$ songs having lengths $[5,7,4]$ and beauty values $[11,14,6]$ is equal to $(5+7+4) \cdot 6 = 96$.

You need to choose at most $k$ songs from your playlist, so the pleasure of listening to the set of these songs them is maximum possible.

Input Format

The first line contains the number of test cases, $t$.

In each test case:

The first line contains two integers $n$ and $k$ ($1 \leq k \leq n ≤ 3 \cdot 10^5$) – the number of songs in the playlist and the maximum number of songs you can choose, respectively.

Each of the next $n$ lines contains two integers $t_i$ and $b_i$ ($1 \leq t_i, b_i \leq 10^6$) — the length and beauty of the $i^{th}$ song.

Sample Input

1
4 3
4 7
15 1
3 6
6 8

Output Format

For each test case, print one integer — the maximum pleasure you can get.

Sample Output

78