AT_cf_2015_morning_hard_h ありんこ

[problemUrl]: https://atcoder.jp/contests/code-festival-2015-morning-hard/tasks/cf_2015_morning_hard_h りんごさんは無限に長い棒の上を歩く $ N $ 匹のアリを眺めています。今、$ i $ 匹目のアリは座標 $ X_i $ の場所にいて、速度 $ S_i $ で方向 $ D_i $ を向いて歩いています。$ D_i $ が `R` のときは座標が増加する向き、$ D_i $ が `L` のときは座標が減少する向きを表します。 りんごさんは $ K $ 匹のアリを棒から取り除くことができます。このとき、はじめにアリどうしが衝突するまでの時間の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ X_1 $ $ S_1 $ $ D_1 $ $ X_2 $ $ S_2 $ $ D_2 $ : $ X_N $ $ S_N $ $ D_N $ - $ 1 $ 行目には、$ 2 $ つの整数 $ N\ (2\ ≦\ N\ ≦\ 10^5),\ K\ (1\ ≦\ K\ ≦\ N-1) $ が空白区切りで与えられる。これは、アリが $ N $ 匹、りんごさんが取り除くことのできるアリが $ K $ 匹であることを表す。 - $ 2 $ 行目からの $ 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 $ にいて、速度 $ S_i $ で方向 $ D_i $ を向いて歩くことを表す。ただし、$ X_i $ は全て相異なることが保証される。

はじめにアリどうしが衝突するまでの時間の最大値を $ 1 $ 行に出力せよ。出力は絶対誤差あるいは相対誤差の少なくとも片方が $ 10^{−6} $ 以下であれば許容される。アリどうしが衝突しないようにすることができる場合は、代わりに `Infinity` と出力せよ。出力の末尾に改行を入れること。

### Sample Explanation 1 $ 2 $ 匹目のアリを取り除いたとき、はじめにアリどうしが衝突するまでの時間が最も長くなります。 ### Sample Explanation 2 小数点以下は何桁出力してもかまいません。