AT_m_solutions2020_e M's Solution

[problemUrl]: https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_e 新 AtCoder 市は以下のように、無限に広がる碁盤の目のような構造になっています。 - 新 AtCoder 市の中心には時計台があり、この座標を $ (0,\ 0) $ とする。 - 時計台を通る東西方向に一直線の道路があり、これを「東西大通り」とする。これは $ 2 $ 次元座標平面では $ x $ 軸に相当する。 - そのほかにも、東西大通りに平行な道路が、距離 $ 1 $ ずつ間隔をあけて無限本存在する。これらは、直線 $ y\ =\ (0\ 以外の整数) $ に相当する。 - 時計台を通る南北方向に一直線の道路があり、これを「南北大通り」とする。これは $ 2 $ 次元座標平面では $ y $ 軸に相当する。 - そのほかにも、南北大通りに平行な道路が、距離 $ 1 $ ずつ間隔をあけて無限本存在する。これらは、直線 $ x\ =\ (0\ 以外の整数) $ に相当する。 新 AtCoder 市には $ N $ 個の集落があります。$ i $ 個目の集落は、座標 $ (X_i,\ Y_i) $ の交差点上にあり、人口は $ P_i $ です。各市民は、これらの集落のうちいずれかひとつに住んでいます。 **現時点で、鉄道路線は東西大通りに沿って無限に延びるものと、南北大通りに沿って無限に延びるものの $ 2 $ 本しかありません。** 市長の M 君は、これでは通勤に不便だと考えたので、新たに $ K $ 本の通りを選んで、それぞれに沿って無限に延びる鉄道路線を建設することにしました。 ここで、新 AtCoder 市の各市民の「歩行距離」を、住んでいる集落から最も近い鉄道路線までの距離とします。 このとき、全ての市民の歩行距離の合計 $ S $ が最も小さくなるように鉄道路線を建設したいです。 さて、$ K\ =\ 0,\ 1,\ 2,\ \dots,\ N $ のそれぞれについて、鉄道路線建設後の $ S $ の最小値はいくつでしょうか？

入力は以下の形式で標準入力から与えられます。 > $ N $ $ X_1 $ $ Y_1 $ $ P_1 $ $ X_2 $ $ Y_2 $ $ P_2 $ $ : $ $ : $ $ : $ $ X_N $ $ Y_N $ $ P_N $

答えを $ N+1 $ 行に出力してください。 $ i $ 行目 $ (i\ =\ 1,\ \ldots,\ N+1) $ には、$ K\ =\ i\ -\ 1 $ の場合の鉄道路線建設後の $ S $ の最小値を整数として出力してください。

### 制約 - $ 1\ \leq\ N\ \leq\ 15 $ - $ -10\ 000\ \leq\ X_i\ \leq\ 10\ 000 $ - $ -10\ 000\ \leq\ Y_i\ \leq\ 10\ 000 $ - $ 1\ \leq\ P_i\ \leq\ 1\ 000\ 000 $ - $ N $ 個の集落の場所 $ (X_i,\ Y_i) $ はすべて異なる - 入力はすべて整数 ### Sample Explanation 1 $ K\ =\ 0 $ の場合、集落 $ 1,\ 2,\ 3 $ の住民は、鉄道路線にたどり着くためには、それぞれ距離 $ 1,\ 3,\ 1 $ 歩く必要があります。 したがって、全ての市民の歩行距離の合計 $ S $ は $ 1\ \times\ 300\ +\ 3\ \times\ 600\ +\ 1\ \times\ 800\ =\ 2900 $ となります。 $ K\ =\ 1 $ の場合、東西大通りから距離 $ 4 $ だけ北の道路に鉄道路線を建設すると、集落 $ 1,\ 2,\ 3 $ の住民の歩行距離は $ 1,\ 1,\ 0 $ になります。 すると、$ S\ =\ 1\ \times\ 300\ +\ 1\ \times\ 600\ +\ 0\ \times\ 800\ =\ 900 $ となります。 他にも多くの候補から建設場所を選べますが、そのうちどれも $ S $ を $ 900 $ より小さくすることはできません。 $ K\ =\ 2 $ の場合、南北大通りから距離 $ 1,\ 3 $ だけ東の道路に鉄道路線を建設すると、新 AtCoder 市のすべての住民が歩行距離 $ 0 $ で鉄道路線にたどり着くことができるので、$ S\ =\ 0 $ となります。また、$ K\ =\ 3 $ の場合も、$ S\ =\ 0 $ とすることができます。 $ K\ =\ 0,\ 1,\ 2 $ の場合の最適な鉄道路線の建設方法を下図に示します。 青く塗られた道路が鉄道路線を敷設する道路を表します。 !\[\](https://img.atcoder.jp/m-solutions2020/fc274bed71a4c37706550fa083496d39.png) ### Sample Explanation 2 $ K\ =\ 1,\ 2 $ の場合の最適な鉄道路線の建設方法を下図に示します。 !\[\](https://img.atcoder.jp/m-solutions2020/7c6b7a31998a1c46fba4c0679b023822.png) ### Sample Explanation 3 $ K\ =\ 3 $ の場合の最適な鉄道路線の建設方法を下図に示します。 !\[\](https://img.atcoder.jp/m-solutions2020/0453fa9c2f02c3bd5d5f9e20d0e8e589.png) ### Sample Explanation 4 $ K\ =\ 4 $ の場合の最適な鉄道路線の建設方法を下図に示します。 !\[\](https://img.atcoder.jp/m-solutions2020/464ce76d1d7d72638eb372342f8386c5.png)