Is there an efficient way to solve this discrete optimization problem?

Question

Let $a_1,\ldots,a_n$ be positive integers with $1\leqslant a_i\leqslant M$ for each $i$ ($M$ being a fixed positive integer greater than $1$), and $C$ a positive integer with $C>M$. I want to solve the integer program \begin{align} \max &\quad\sum_{j=1}^n x_j\\ \mathrm{s.t.}&\quad Cx_j\leqslant \sum_{i=1}^n a_iy_{ij},\quad 1\leqslant j\leqslant n\\ &\quad \sum_{j=1}^n y_{ij} \leqslant 1,\quad 1\leqslant i\leqslant n\\ &\quad x_j\in\{0,1\},\quad 1\leqslant j\leqslant n\\ &\quad y_{ij}\in\{0,1\},\quad 1\leqslant i,j\leqslant n \end{align} In my particular application, $M=19$ and $C=40$. So for example, if $a_1=a_2=a_3=a_4=15$ and $a_5=a_6=a_7=a_8=6$ then an optimal solution would be \begin{align} x_1 &= 1\\ x_2 &= 1\\ y_{11} &= 1\\ y_{12} &= 1\\ y_{15} &= 1\\ y_{16} &= 1\\ y_{23} &= 1\\ y_{24} &= 1\\ y_{27} &= 1\\ y_{28} &= 1\\ \end{align} I'm thinking there should be some sort of dynamic programming approach that would be relatively straightforward to implement (as opposed to actually solving the IP).