质疑概率

Problem Description

小 Q 最近正在进行大量的氪金抽卡行为以获取 RPG 游戏中的各种稀有道具。他把先后开启 $n$ 袋卡的全过程录制成了一个视频，开启的第 $i$ 袋包含 $a_i$ 张卡片，其中有 $b_i$ 张卡片中奖。在打开全部 $n$ 袋卡之后，小 Q 觉得自己的体感中奖率与官方公布的中奖率不符。于是，小 Q 准备将视频分割成恰好 $k$ 个切片，每个切片包含完整地开启编号连续的若干袋卡的过程，并将每个切片分别作为一个独立视频公开。不同切片包含的卡袋数可以不同，但不允许出现空的切片。 最后，小 Q 将分别统计每个切片内的实际中奖率，找出其中的最大值 $\frac{P}{Q}$，并向官方提出质疑：“我这 $k$ 段视频的中奖率最高也不过是 $\frac{P}{Q}$。” $\frac{P}{Q}$ 越低，对官方造成的压力越大。请写一个程序，帮助小 Q 找到最优的视频分段方式，使得 $\frac{P}{Q}$ 最小。

Input

第一行包含一个正整数 $T$（$1\leq T\leq 500$），表示测试数据的组数。 每组数据第一行包含两个正整数 $n,k$（$1\leq k\leq n\leq 100\,000$），分别表示卡袋数以及视频切片数。 接下来 $n$ 行，每行两个整数 $a_i,b_i$（$1\leq a_i\leq 1000$, $0\leq b_i\leq a_i$），分别表示开启的第 $i$ 袋包含的卡片数以及其中中奖的卡片数。 输入数据保证 $\sum n\leq 1\,000\,000$。

Output

对于每组数据输出一行一个既约分数 “$\texttt{P/Q}$”，表示 $\frac{P}{Q}$ 的最小可能值。

Sample Input

3
2 1
3 0
2 0
2 1
3 3
2 2
4 2
1 1
1 0
2 0
1 1

Sample Output

0/1
1/1
1/2

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（7）