ISL 2010 C7

Let $P_{1}, \ldots, P_{s}$ be arithmetic progressions of integers, the following conditions being satisfied: (i) each integer belongs to at least one of them; (ii) each progression contains a number which does not belong to other progressions. Denote by $n$ the least common multiple of steps of these progressions; let $n=p_{1}^{\alpha_{1}} \ldots p_{k}^{\alpha_{k}}$ be its prime factorization. Prove that $$s \geq 1+\sum_{i=1}^{k} \alpha_{i}\left(p_{i}-1\right)$$ (Germany)