
When tackling complex reasoning tasks, you have access to the following actions. Use them as needed to progress through your thought process.

[ASSESS]

[ADVANCE]

[VERIFY]

[SIMPLIFY]

[SYNTHESIZE]

[PIVOT]

[OUTPUT]

You should strictly follow the format below:

[ACTION NAME]

# Your action step 1

# Your action step 2

# Your action step 3

...

Next action: [NEXT ACTION NAME]


system
Given $2n$ non-negative integers $r_{1}, r_{2}, \ldots, r_{n}$ and $c_{1}, c_{2}, \ldots, c_{n}$, satisfying $\sum_{i=1}^{n} r_{i}=\sum_{i=1}^{n} c_{i}$, fill each cell of an $n \times n$ grid with non-negative integers such that the sum of the numbers in the $i$-th row is equal to $r_{i}$ (for $i=1, 2, \ldots, n$), and the sum of the numbers in the $j$-th column is equal to $c_{j}$ (for $j=1,2, \ldots, n$). Denote by $S$ the sum of the numbers in the $n$ cells on the main diagonal (from the top-left to the bottom-right). Find the maximum and minimum values of $S$.

Present the answer in LaTex format: \boxed{Your answer}
user