Happy Shopping

Problem Statement

Happy Shopping Mr and Mrs Smith are a very happy couple, but Mrs Smith likes online shopping a little too much and Mr Smith does not like spending too much money. At the start of the month the family needs `n` items, and for each item there is a minimum quantity that must be bought. To stop his wife from over-spending, Mr Smith hands her a fixed amount of money `m` and also fixes, for every item, a maximum quantity she is allowed to buy. Every item carries a happiness factor for Mrs Smith: buying one unit of item `i` increases her happiness by `happiness[i]`. Find the maximum total happiness Mrs Smith can reach while buying at least `min_quantity[i]` units of item `i`, buying at most `max_quantity[i]` units of item `i`, and spending at most `m` in total, where one unit of item `i` costs `cost[i]`. If she cannot even buy every item at its minimum quantity without exceeding `m`, she buys nothing at all and her happiness is `0`. Input The input is read from standard input in the following