Solution:

Adding the equation $x^2 - y - k = 0$ to $\frac{1}{2}$ times $2(y - 20)^2 - x - k = 0$ gives a conic through all intersection points with equal $x^2$ and $y^2$ coefficients: $$x^2 + y^2 - \tfrac{1}{2}x - 41y + 400 - \tfrac{3k}{2} = 0,$$ a circle centered at $\left(\frac{1}{4}, \frac{41}{2}\right)$ with squared radius $\frac{1}{16} + \frac{1681}{4} - 400 + \frac{3k}{2} = \frac{325}{16} + \frac{3k}{2}.$ So whenever four distinct intersection points exist, they are concyclic, and the radius is at most $21$ exactly when $\frac{325}{16} + \frac{3k}{2} \le 441,$ i.e. $k \le 280$ for integers.

Substituting $y = x^2 - k$ into the second parabola gives the quartic $f(x) = 2(x^2 - c)^2 - x - k = 0$ where $c = k + 20.$ For $1 \le k \le 4:$ if $x \le -k$ then $f(x) = 2(x^2 - c)^2 + (-x - k) \gt 0,$ and if $-k \lt x \le 0$ then $x^2 \lt 16$ while $c \ge 21,$ so $f(x) \gt 2 \cdot 25 - k \gt 0;$ thus there are no intersections with $x \le 0,$ and since $f'(x) = 8x^3 - 8cx - 1$ has exactly one positive root, $f$ has at most (and, by $f(0) \gt 0,$ $f(\sqrt{c}) \lt 0,$ exactly) two positive roots. So $k \le 4$ fails. For $k \ge 5,$ we have $k^2 \ge k + 20,$ so $f\left(-\sqrt{c}\right) = \sqrt{c} - k \le 0$ with $f$ strictly decreasing there, while $f(-\infty) = +\infty,$ $f(0) = 2c^2 - k \gt 0,$ $f\left(\sqrt{c}\right) = -\sqrt{c} - k \lt 0,$ and $f(+\infty) = +\infty:$ the sign changes produce four distinct real roots.

Hence $S = \{5, 6, \ldots, 280\},$ and the answer is $5 + 280 = 285.$