There are $n$ snails on the plane where the $i$ snail has $a_i$ attack and $d_i$ defense, where $a_i, d_i\in \mathbb{R}$ and each snail has a distinct attack and a distinct defense. We said a 4-tuple of subsets of snails $(S_1, S_2, S_3, S_4)$ is balanced if $|S_1|+|S_3|$ is either $\lceil n/2\rceil$ or $\lfloor n/2\rfloor$ and there exist real numbers $A, D$ such that \begin{align*} S_1=\{i\ |\ a_i\geq A\text{ and } d_i\geq D, 1\leq i\leq n\}\\ S_2=\{i\ |\ a_i<A\text{ and } d_i\geq D, 1\leq i\leq n\}\\ S_3=\{i\ |\ a_i< A\text{ and } d_i< D, 1\leq i\leq n\}\\ S_4=\{i\ |\ a_i\geq A\text{ and } d_i< D, 1\leq i\leq n\} \end{align*}Find the largest integer $k$ such that there is always at least $k$ balanced 4-tuples of subsets. Proposed by redshrimp