题目简介

苹果先生正在观察着站在无限长棒子上的 $N$ 只蚂蚁。现在，第 $i$ 只蚂蚁位于坐标 $X_i$，并以速度 $S_i$ 和方向 $D_i$ 前进。当 $D_i$ 为 $R$ 时，表示坐标增加的方向；当 $D_i$ 为 $L$ 时，表示坐标减少的方向。 苹果先生可以挑选出 $K$ 只蚂蚁将其移除。请您计算出蚂蚁相撞前的最长时间。

输入格式

输入从标准输入中给出，格式如下：

第一行包含两个整数 $N (2 <= N <= 10^5)$ 和 $K (1 <= K <= N-1)$，表示蚂蚁总数和挑选出的蚂蚁数。

接下来的 $N$ 行给出了蚂蚁的信息。其中第 $i$ 行$(1 <= i <= N)$包含了整数 $X_i (0 <= X_i <= 10^9)$、$S_i (1 <= S_i <= 10^6)$ 和字符 $D_i$ （$D_i$ 是 $L$ 或 $R$），表示第 $i$ 只蚂蚁的初始坐标、速度和方向。保证所有的 $X_i$ 不重复。

输出格式

输出结果应该从标准输出中输出，只包含一行，表示蚂蚁相撞前的最长时间。如果无法避免蚂蚁相撞，则输出 Infinity。最终输出应以换行符结束。

@yjjr @chen_zhe