手裏剣を全く使わない場合、\(i\) 番目の魔物と戦うことで減る体力は \(a_i(b_i +x_i - 1)\) と表せます。
手裏剣を使うことで体力の減少をどれだけ抑えられるか考えてみましょう。

\(x_i = 0\) のとき

手裏剣を \(b_i\) 枚以上投げる必要はありません。手裏剣を \(k \, (1 \leq k \leq b_i - 1)\) 枚投げることで、体力の減少を \(ka_i\) だけ抑えることができます。

\(x_i = 1\) のとき

\(b_i = 1\) のとき、手裏剣を \(2\) 枚以上投げる必要はなく、\(1\) 枚投げることで体力の減少を \(a_i\) だけ抑えることができます。

\(b_i \geq 2\) のとき、手裏剣を \(1\) 枚だけ投げると体力が \(b_i - 1\) の地上にいる魔物になります。よって体力の減少を \(2a_i\) だけ抑えることができます。
この状態からは手裏剣を \(b_i - 1\) 枚以上投げる必要はなく、さらに \(k \, (1 \leq k \leq b_i - 2)\) 枚投げることで体力の減少を \(ka_i\) だけ抑えることができます。

「手裏剣を \(1\) 枚投げることで体力の減少を最も多く抑えられるような魔物に投げる」ことを繰り返すのが最適です。実際に \(1\) 枚ずつ投げていると計算量が \(\Theta(M)\) となってしまいますが、手裏剣を投げるべき魔物がずっと変わらない場合は複数回投げる処理をまとめて行うことで、\(O(N)\) で解くことができます。