　平面上のいくつかの点の集合について, どの $3$ 点も同一直線上になくどの $4$ 点も同一円周上にないとき, これを**整った**と呼ぶこととする. 以下, 単に**円**や**三角形**などといえば, その頂点は整った点の集合から選ばれた $3$ 点であるとする.

----
**補題1.**　整った $s$ 個の点に対して, 他のすべての点を内部に含む円が存在する. つまり $M=s-3$ である.\
**証明.**　$s$ 個の点の凸包を $P_1\cdots P_k$ とし, $\angle{P_1P_3P_2},\cdots,\angle{P_1P_kP_2}$ のうち大きさが最小であるものを $\angle{P_1P_iP_2}$ とすれば, $P_1,P_2,P_i$ を通る円は他の $s-3$ 個の点を内部に含む.

----
**補題2.**　整った $s$ 個の点の凸包が $t$ 角形となることと, $f(s-3)=t-2$ が成り立つことは同値である.\
**証明.**　左から右を示せば逆は明らかに従う. まず, 相異なる三角形のそれぞれ外接円がともに他のすべての点を内部に含むとき, $2$ つの三角形の辺は交わらないことが容易にわかる. また, 外接円が他のすべての点を内部に含むような三角形たちで, 凸包である $2n$ 角形の三角形分割を構成できることが分かる. 以上を併せることで示された.

----
　整ったいくつかの点 $S$ に対して, すべての円の内部の点の個数の総和を $S$ の**重さ**と呼ぶこととする.\
　また, 同様にすべての三角形の内部の点の個数の総和を $S$ の**密度**と呼ぶこととする. 

----
**補題3.**　整った $s\geq 4$ 個の点の重さを $G$ とし, 密度を $D$ とすると, 配置によらず $G+D=2\times{\_s}\mathrm{C}\_4$ が成り立つ.\
**証明.**　$s$ 個の点を $P_1,\cdots,P_s$ とし, $P_k$ を除いた $s-1$ 点の重さを $G_k$, 密度を $D_k$ とする. ${\_s}\mathrm{C}\_3$ 個の円のうちある一つ $C$ に着目すれば, その内部の点は $G_1,\cdots,G_s$ において $s-4$ 回重複してカウントされるから,
$$(s-4)G=\sum_{k=1}^{s}G_k$$
また同様な議論から次も成り立つ
三角形についても同様に議論することで, 結局以下を得る.
$$(s-4)(G+D)=\sum_{k=1}^{s}(G_k+D_k)$$
よって, $s=4$ のとき常に $G+D=2$であることとに留意すれば, 帰納的に成立が示される.

----
　 以下, 整った $2n$ 個の点に一般化して議論を進める. すなわち条件は $f(M)=n$ であるから, 補題1,2より凸包は $n+2$ 角形である. $2n$ 個の点の重さを $G$, 密度を $D$ とすると, 補題3より $G=2\times{\_{2n}}\mathrm{C}\_4-D$ であり, 求める
$$f(1)+2f(2)+\cdots+(M-1)f(M-1)+Mf(M)$$
の最大値は $G$ の最大値と等しいから, $D$ の最小値を求めればよい.\
　まず$D\geq (n-2)(2n-3)$ を示す. 凸  $n+2$ 角形の内部の点 $P$ について, $n+2$ 角形の頂点からなり, $P$ を内部に含むような三角形は少なくとも $n$ 個存在する. また $P$ と $n+2$ 角形の頂点をそれぞれ結んだとき, $n+2$ 角形の内部は $n+2$ 個の三角形によって分割されるので, 内部に他の点 $Q$ があったとき, $P$ と $n+2$ 角形の頂点からなる三角形であって $Q$ を内部に含むようなものが必ず存在する.
よって
$$D\geq n(n-2)+(n-3)(n-2)=(n-2)(2n-3)$$
　逆に $D=(n-2)(2n-3)$ をみたす配置が存在する. $2n$ 個の点の凸包である凸 $n+2$ 角形を$P_1\cdots P_{n+2}$ とし, 任意の $i$ について, $P_iP_{i+1},P_iP_{i+2},P_{i+1}P_{i-1}$ に囲まれた領域内に $Q_iQ_{i+1}\parallel P_iP_{i+2}$ をみたすように $Q_i$ を適当にとり, 凸包の内部にある $n-2$ 個の点を $Q_1,\cdots,Q_{n+2}$ の中から選べばよい.\
　以上より $G$ の最大値は $2\times{\_{2n}}\mathrm{C}\_4-(n-2)(2n-3)$ であるから, $n=500$ を代入して $\textbf{82833752994}$.
公式解説
https://onlinemathcontest.com/contests/omckoukou1/editorial/2150
　平面上に $1000$ 個の点があり, どの $3$ 点も同一直線上になく, どの $4$ 点も同一円周上にありません. ここから $3$ 点を選ぶ方法であって, それらを通る円の内部 (周上を含まない) にちょうど $k$ 個の点を含むようなものの個数を $f(k)$ で表します. いま, $3$ 点を通る円が内部に含むことのできる点の個数の最大値を $M$ とすると, $f(M)=500$ が成立しました. このとき, 以下のとりえる最大値を求めてください. 
$$f(1)+2f(2)+\cdots+(M-1)f(M-1)+Mf(M)$$