Let $G$ be a graph on $n$ vertices with $m$ edges, and let $C$ be a collection of cliques whose union is $G$ and such that $\kappa = \sum_{c \in C}|c|$ is minimal.
Is it true that necessarily $\kappa \leq 2 \lfloor n/2\rfloor \lceil n/2 \rceil $?
Note: a trivial bound is $\kappa \leq 2\cdot m \le n(n-1)$.