First we establish the upper bound by exhibiting a 3-(total-)coloring for $C_n$ when $3\mid n$ and a 4-coloring for all $n$.
When $n\mid 3$ color the vertices red, green, blue cyclically.
Color the edge between two vertices with the only color that is not used on its endpoints. This is a proper total coloring with 3 colors (verify!).
When $n$ is even we alternately color the vertices with red and green, and we alternately color the edges with blue and yellow.
This is a proper total coloring with 4 colors (verify!).
When $n$ is odd we go clockwise around the cycle and start coloring vertices alternately with red and green. The last vertex would cause two adjacent red vertices, so we color it blue instead. Now we walk around the cycle again and when we go from a red to a green vertex we color the edge blue, when we go from a green to a red vertex we color the edge blue, when we go from a green to a blue vertex (only once) we color the edge red and when we go from a blue to a red vertex (only once) we color the edge green.
This is a proper total coloring with 4 colors (verify!).
Since $\chi''(G)\geq\Delta(G)+1=3$ we are already done with the case $3\mid n$.
For the last part we need to show that no proper 3-total-coloring is possible,
unless $n$ is a multiple of 3.
Let $v_1,\ldots,v_n$ be the vertices of $C_n$ and assume we have a proper 3-coloring. $v_1$, $v_2$ and edge $v_1v_2$ must have all different colors, say red, green, blue respectively. Now edge $v_2v_3$ cannot be green or blue, so it must be red. Vertex $v_3$ cannot be green or red, so it must be blue. Continuing this process you see that the entire coloring is forced and that we end up with a cyclic coloring of the vertices with period three just as we used above (verify!). Clearly this is only possible when $n$ is a multiple of 3.
Best Answer
Pick a coloring using $\chi (G)$ color, then $$E(G)=\sum _{i=1}^{\chi (G)}\text{# of edges colored with color }i.$$ Notice now that the edges colored with one color form a matching on the graph, but this quantity is bounded by $m,$ so $$E(G)=\sum _{i=1}^{\chi (G)}\text{# of edges colored with color }i\leq m\cdot \chi (G).$$