AT_past202212_j 横断

You are given points $ S(x_{\mathrm{s}}, y_{\mathrm{s}}) $ and $ T(x_{\mathrm{t}}, y_{\mathrm{t}}) $ in the $ xy $ -plane. You are also given $ N $ four-tuples $ (P_i, Q_i, R_i, W_i)(1 \leq i \leq N) $ . Consider the following procedure. - First, choose an arbitrary (directed) curve $ C $ from point $ S(x_{\mathrm{s}}, y_{\mathrm{s}}) $ to $ T(x_{\mathrm{t}}, y_{\mathrm{t}}) $ - Next, choose arbitrary $ K $ **distinct** integers $ A_1, A_2, \ldots, A_K $ between $ 1 $ and $ N $ . - Then, for each $ i = 1, 2, \ldots, K $ , do the following: - If the curve $ C $ has one or more common points with the line $ P_{A_i} x + Q_{A_i} y = R_{A_i} $ , you pay $ W_{A_i} $ yen (the currency in Japan). Print the minimum possible amount of money you pay in total in the procedure above.

The input is given from Standard Input in the following format: > $ 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 $

Print the answer.

### Sample Explanation 1 Consider the case where you choose a path along the $ x $ -axis from point $ S(-2, 0) $ to $ T(2, 0) $ as the curve $ C $ , and integers $ 2, 3, 4 $ as the $ 3 $ distinct integers between $ 1 $ and $ 4 $ . Then, - The curve $ C $ does not have a common point with the line $ P_2 x + Q_2 y = R_2 $ (i.e. the line $ y = 10 $ ). - The curve $ C $ has a common point $ (-1, 0) $ with the line $ P_3 x + Q_3 y = R_3 $ (i.e. the line $ x = -1 $ ), so you pay $ W_3 = 3 $ yen. - The curve $ C $ has a common point $ (0, 0) $ with the line $ P_4 x + Q_4 y = R_4 $ (i.e. the line $ -x + y = 0 $ ), so you pay $ W_4 = 5 $ yen. Therefore, you pay $ 8 $ yen in total, which is the minimum possible amount. ### Sample Explanation 2 Point $ S $ and point $ T $ may be the same point. Also, lines $ P_i x + Q_i y = R_i $ may be identical for multiple different $ i $ 's. ### 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 $ or $ Q_i \neq 0 $ . - For all $ i = 1, 2, \ldots, N $ , neither point $ S $ nor point $ T $ is on the line $ P_i x + Q_i y = R_i $ . - All values in the input are integers.