Problem J: Demon's Plan

BackGround

デーモンズプランでは慾を司る108体の悪魔が日夜プログラミングコンテストでしのぎを削っている。主催であるパトローンは、全ての慾が集う場所”リクス＝マグナ”に悪魔たちを招待しようとしている。 パトローンはまだ招待を送っていない悪魔に招待を送りたいが、悪魔は世界各地におり、自分で行くのは面倒くさいので自身の使い魔達にやらせることにした。 パトローンは気が利くので使い魔同士がより平等に働くようにどの使い魔がどの悪魔を担当するかを割り振ろうとしている。

Problem

N体の使い魔とM体の悪魔がいる。 使い魔_i と 悪魔_j の距離は H_{i j}である。

各悪魔に必ず1人の使い魔を向かわせたい。どの使い魔がどの悪魔を訪問するかは以下の条件に従って割り振ることにした。

1. 使い魔1体あたりの訪問する悪魔の数の差の最大を最小化する。
2. 1を満たした上で訪問する悪魔と担当する使い魔の距離の最大を最小化する。

1行目に使い魔1体あたりの訪問する悪魔の数の差の最大を、2行目に悪魔と担当する使い魔の距離の最大を出力せよ。

Input

入力は以下の形式で与えられる。

N M
H0 0 H0 1 … H0 M−1
H1 0 H1 1 … H1 M−1
.
.
HN−1 0 HN−1 1 … HN−1 M−1

1行目に使い魔の数Nと悪魔の数Mが整数で空白区切りで与えられる。 続くN行に使い魔と悪魔の距離が整数で与えられる。H_ijは使い魔_iと悪魔_jの距離を表す。

Constraints

• 1 ≤ N ≤ 108
• 1 ≤ M ≤ 108
• 1 ≤ H_{i j} ≤ 10⁹ ( 0 ≤ i < N, 0 ≤ j < M ) ( 使い魔iから悪魔jまでの距離 )

Output

問題文の条件に従い、1行目に使い魔1体あたりの訪問する悪魔の数の差の最大を、2行目に悪魔と担当する使い魔の距離の最大を出力せよ。

Sample Input 1

3 3
1 2 3
2 1 2
3 2 1

Sample Output 1

0
1

使い魔₀ - 悪魔₀
使い魔₁ - 悪魔₁
使い魔₂ - 悪魔₂
と割り振ることで訪問する悪魔の数の差が0になり、担当使い魔と悪魔の距離の最大が1になり最適な組み合わせになる。

Sample Input 2

3 5
1 2 3 4 5
5 4 3 2 1
4 3 2 1 5

Sample Output 2

1
2

使い魔₀ - 悪魔₀
使い魔₀ - 悪魔₁
使い魔₁ - 悪魔₄
使い魔₂ - 悪魔₃
使い魔₂ - 悪魔₂
と割り振ることで訪問する悪魔の差が1になり、担当使い魔と悪魔の距離の最大が2になり最適な組み合わせになる。

Note

Link

 

---