Kinugoshi's Break Fast

種類ごとの満足度を前計算しておくことを考えます。
満足度の計算式が 料理のおいしさ $\times$ ジャンルの好きさ なので、
他に何の料理を食べたとしても変わらないため前計算が可能です。
すると、満足度を $value$ 、腹持ちを $weight$ としたナップサックDPになるため、 この問題を $O(NM)$ で解くことができました。
オーバーフローに注意しましょう。