3. At a banquet of a university, there are 2017 mathematicians, each with two different main courses on their order menu, and no two people have the same pair of main courses on their menu. The price of each main course is equal to the number of mathematicians who ordered that main course. The university pays for the cheaper of the two main courses for each mathematician (if the prices are the same, either can be chosen). For all possible sets of order menus, find the maximum total payment of the university.
3. Reformulate the problem using graph theory: For any graph $G$ with 2017 edges, find
$S(G) \triangleq \sum_{e=r w} \min \{\operatorname{deg} v, \operatorname{deg} w\}$

the maximum value.
The following proof shows that the maximum value is $63 \mathrm{C}_{64}^{2}+1=127009$.
Define the graph $L_{k}: L_{k}$ contains $k+1$ vertices, where $k$ vertices form a complete graph and the $(k+1)$-th vertex is connected to exactly one of the $k$ vertices.
Then $L_{k}$ contains $\mathrm{C}_{k}^{2}+1$ edges, and
$S\left(L_{k}\right)=(k-1) \mathrm{C}_{k}^{2}+1$.
In particular, $L_{64}$ satisfies that it contains 2017 edges, and
$S\left(L_{64}\right)=127009$.
We will prove two lemmas.
Lemma 1 Suppose the graph $G$ has 2017 edges and $n$ vertices, with degrees of each vertex arranged in non-increasing order as $d_{1}, d_{2}, \cdots, d_{n}$. Then $n \geqslant 65$, and
$S(G) \leqslant d_{2}+2 d_{3}+\cdots+63 d_{64}+d_{65}$.
Proof of Lemma 1: Since $\mathrm{C}_{64}^{2}x_{i+1} \geqslant x_{j-1}>x_{j}$,

then replacing $\left(x_{i}, x_{j}\right)$ with $\left(x_{i}-1, x_{j}+1\right)$ still satisfies the condition, but $A$ strictly increases. Thus, we can assume that the difference between any two of $x_{1}$, $x_{2}, \cdots, x_{64}$ (the larger minus the smaller) is at most 1.

If $x_{65} \geqslant 4$, then replacing $\left(x_{1}, x_{2}, x_{3}, x_{4}, x_{65}\right)$ with $\left(x_{1}+1, x_{2}+1, x_{3}+1, x_{4}+1, x_{65}-4\right)$ still satisfies the condition, but $A$ strictly increases. Thus, we can assume $x_{65} \leqslant 3$.
Assume $\sum_{i=1}^{65} x_{i}=4034$, otherwise, we can increase $x_{1}$. Thus, there are only the following four possible cases.
(1) $x_{1}=x_{2}=\cdots=x_{63}=63, x_{64}=62, x_{65}=3$, then $A=126948$;
(2) $x_{1}=x_{2}=\cdots=x_{64}=63, x_{65}=2$, then $A=127010$;
(3) $x_{1}=64, x_{2}=x_{3}=\cdots=x_{64}=63, x_{65}=1$, then $A=127009$;
(4) $x_{1}=x_{2}=64, x_{3}=x_{4}=\cdots=x_{64}=63, x_{65}=0$, then $A=127009$.
From the above, we know $A \leqslant 127010$, and equality holds only in case (2).
Lemmas 1 and 2 are proved.
By Lemmas 1 and 2, for all graphs $G$ satisfying the conditions, we have
$S(G) \leqslant 127010$.
Next, we need to prove that equality does not hold.
Retaining the boundary conditions for $d_{i}$ and $a_{i}$, we have
$$
d_{1}=d_{2}=\cdots=d_{64}=63, d_{65}=2
$$
(Specifically, we can remove isolated vertices from the graph $G$, so we can assume $n=65$). Then, by definition,
$$
\begin{array}{l}
a_{i} \leqslant i-1(i=1,2, \cdots, 64), \text { and } a_{65}=2 . \\
\text { Hence } S(G)=\sum_{i=1}^{n} a_{i} d_{i} \\
=63\left(a_{1}+a_{2}+\cdots+a_{64}\right)+a_{65} \\
=63\left(2017-a_{65}\right)+a_{65} \\
=63 \times 2015+2=126947,
\end{array}
$$