Editor's note: This editorial has been adapted from https://atcoder.jp/contests/arc201/editorial/13373.

We can assume there are infinitely many dummy mineral chunks with any integer mass and value ~0~, so we only need to consider choosing mineral chunks such that the sum of masses is exactly ~M~.

When ~\min(m_i) > 1~, we can divide both ~M~ and all mineral chunk masses by ~\min(m_i)~ without changing the answer. (If ~M~ is not divisible by ~\min(m_i)~, we replace ~M~ with ~\lfloor M/\min(m_i) \rfloor~.)

Suppose the two lowest masses are ~1~ and ~x~. When ~M~ is divisible by ~x~, the number of mineral chunks with mass ~1~ that we choose must be divisible by ~x~. In this case, it's clearly optimal to choose them in descending order of value. In other words, we can form groups of ~x~ mineral chunks with mass ~1~, in descending order of value, treating each group as a single mineral chunk with mass ~x~. By performing this operation, all masses become divisible by ~x~, so we can divide both ~M~ and all mineral chunk masses by ~x~ without changing the answer.

When ~M~ is not divisible by ~x~, we need to choose ~M \bmod x~ mineral chunks with mass ~1~. In this case, we must choose ~M \bmod x~ mineral chunks with mass ~1~ that have the maximum value, and then we can reduce this to the case where ~M~ is divisible by ~x~.

Lastly, if all mineral chunks have mass ~1~, we can use ~x = \infty~.

By repeating this procedure at most ~\mathcal{O}(\log M)~ times, ~M~ becomes ~0~, and the total value of the chosen mineral chunks at that point is the answer. With a proper implementation, the time complexity is ~\mathcal{O}(N \log N \log M)~.