Description

Farmer John wants to divide his $N$ cows numbered $1 \ldots N$ ($N \leq 7500$) into $K$ non-empty groups ($2 \leq K \leq N$), such that any two cows from different groups must walk some distance to meet each other. Cows $x$ and $y$ (where $1 \leq x<y \leq N$) are willing to walk $(2019201913x+2019201949y) \mod 2019201997$ miles in order to meet.

Given a grouping plan that divides the $N$ cows into $K$ non-empty groups, let $M$ be the minimum number of miles that any two cows from different groups are willing to walk to meet. To test the cows' loyalty to each other, Farmer John wants to divide the $N$ cows into $K$ groups in the best possible way so that $M$ is as large as possible.

Input Format

The input consists of a single line containing $N$ and $K$, separated by a space.

Output Format

Output the optimal value of $M$.

3 2

2019201769

Hint

In this example, cow $1$ and cow $2$ are willing to walk $2019201817$ miles to meet. Cow $2$ and cow $3$ are willing to walk $2019201685$ miles. Cow $1$ and cow $3$ are willing to walk $2019201769$ miles. Therefore, if cow $1$ is put alone in one group, and cows $2$ and $3$ are put into another group, then $M = \min(2019201817, 2019201769) = 2019201769$ (this is the best result we can achieve in this problem).

Translated by ChatGPT 5