[USACO19OPEN] I Would Walk 500 Miles G

Farmer John想要将他的编号为 $ 1 \ldots N $ 的 $ N $ 头奶牛（ $ N \leq 7500 $ ）分为非空的 $ K $ 组（ $ 2 \leq K \leq N $ ），使得任意两头来自不同组的奶牛都需要走一定的距离才能相遇。奶牛 $ x $ 和奶牛 $ y $ （其中 $ 1 \leq x<y \leq N $ ）愿意为了见面走 $ (2019201913x+2019201949y) \mod 2019201997 $ 英里。 给定一个将 $ N $ 头奶牛分为 $ K $ 个非空小组的分组方案，令 $ M $ 为任意两头来自不同组的奶牛愿意为了见面行走的英里数的最小值。为了测试奶牛们相互之间的忠诚度，Farmer John想要将 $ N $ 头奶牛以最佳的方式分为 $ K $ 组，使得 $ M $ 尽可能大。

输入仅有一行，包含 $ N $ 和 $ K $ ，用空格分隔。

输出最优的 $ M $ 。

3 2

2019201769

在这个例子中，奶牛1和奶牛2愿意为了见面走2019201817英里。奶牛2和奶牛3愿意走2019201685英里。奶牛1和奶牛3愿意走2019201769英里。所以，将奶牛1单独分为一组，奶牛2和奶牛3分为一组， $ M=min(2019201817,2019201769)=2019201769 $ （这是我们在这个问题中能够达到的最佳结果）。