BxMO 2015 Problem 4

An arithmetic progression is a set of the form $\{a, a+d, \ldots, a+k d\}$, where $a, d, k$ are positive integers and $k \geqslant 2$. Thus an arithmetic progression has at least three elements and the successive elements have difference $d$, called the common difference of the arithmetic progression.

Let $n$ be a positive integer. For each partition of the set $\{1,2, \ldots, 3 n\}$ into arithmetic progressions, we consider the sum $S$ of the respective common differences of these arithmetic progressions. What is the maximal value $S$ that can attain? (A partition of a set $A$ is a collection of disjoint subsets of $A$ whose union is $A$.)