AT_past202212_j 横断

$ xy $ -平面上の点 $ S(x_{\mathrm{s}}, y_{\mathrm{s}}) $ と点 $ T(x_{\mathrm{t}}, y_{\mathrm{t}}) $ が与えられます。 また、 $ 4 $ つの整数からなる $ N $ 個の組 $ (P_i, Q_i, R_i, W_i)(1 \leq i \leq N) $ が与えられます。 下記の手順を考えます。 - まず、点 $ S(x_{\mathrm{s}}, y_{\mathrm{s}}) $ を始点とし、点 $ T(x_{\mathrm{t}}, y_{\mathrm{t}}) $ を終点とする（有向）曲線 $ C $ を任意に $ 1 $ つ選ぶ - 次に、 $ 1 $ 以上 $ N $ 以下の**相異なる** $ K $ 個の整数 $ A_1, A_2, \ldots, A_K $ を任意に選ぶ。 - その後、 $ i = 1, 2, \ldots, K $ について、下記を行う。 - もし曲線 $ C $ が直線 $ P_{A_i} x + Q_{A_i} y = R_{A_i} $ と $ 1 $ つ以上の共有点を持つならば、 $ W_{A_i} $ 円払う。 上記の手順において支払う合計金額としてあり得る最小値を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ x_{\mathrm{s}} $ $ y_{\mathrm{s}} $ $ x_{\mathrm{t}} $ $ y_{\mathrm{t}} $ $ P_1 $ $ Q_1 $ $ R_1 $ $ W_1 $ $ P_2 $ $ Q_2 $ $ R_2 $ $ W_2 $ $ \vdots $ $ P_N $ $ Q_N $ $ R_N $ $ W_N $

答えを出力せよ。

### Sample Explanation 1 曲線 $ C $ として $ x $ 軸上を点 $ S(-2, 0) $ から $ T(2, 0) $ へ移動する経路を選び、 $ 1 $ 以上 $ 4 $ 以下の相異なる $ 3 $ 個の整数として $ 2, 3, 4 $ を選ぶ場合を考えます。 このとき、 - 曲線 $ C $ は、直線 $ P_2 x + Q_2 y = R_2 $ （すなわち、直線 $ y = 10 $ ）と共有点を持たない。 - 曲線 $ C $ は、直線 $ P_3 x + Q_3 y = R_3 $ （すなわち、直線 $ x = -1 $ ）との共有点 $ (-1, 0) $ を持つため、 $ W_3 = 3 $ 円払う。 - 曲線 $ C $ は、直線 $ P_4 x + Q_4 y = R_4 $ （すなわち、直線 $ -x + y = 0 $ ）と共有点 $ (0, 0) $ を持つため、 $ W_4 = 5 $ 円払う。 よって、支払う合計金額は $ 8 $ 円であり、これが考えられる最小値です。 ### Sample Explanation 2 点 $ S $ と点 $ T $ が同一の点であることや、 異なる複数の $ i $ について直線 $ P_i x + Q_i y = R_i $ が同一の直線であることがあります。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq K \leq N $ - $ -10^9 \leq x_{\mathrm{s}}, y_{\mathrm{s}}, x_{\mathrm{t}}, y_{\mathrm{t}} \leq 10^9 $ - $ -10^9 \leq P_i, Q_i, R_i \leq 10^9 $ - $ 1 \leq W_i \leq 10^9 $ - $ P_i \neq 0 $ または $ Q_i \neq 0 $ - どの $ i = 1, 2, \ldots, N $ についても、点 $ S $ と点 $ T $ はどちらも直線 $ P_i x + Q_i y = R_i $ 上にない - 入力はすべて整数