$2$ Caveat Venditor

Due to dwindling popularity, the world's last DVD store is closing down and having a sale to get

rid of their remaining inventory of movies. Every movie costs the same amount $C$ crowns, and in

addition they have distributed a large number of coupons all over town with offers along the lines

of "Buy any five movies, get two of them for free". This means that you can get any $5$ movies in

the store $($even $5$ copies of the same movie$)$ for a cost of $3*C$ crowns $($instead of $5*C$ crowns$).$

An avid DVD collector wants to buy $n$ of the movies available in the store, and to get the best

deal they have gone around town and collected a large number $m$ of the discount coupons $($for

some reason, nobody else was interested in them$).$ The coupons can have different offerings. E$.$g$.,$

one could be "buy three, get one for free", another could be "buy $100,$ get $5$ for free", etc. Now

the collector has a conundrum: what is the best way to use these coupons in order to get all $n$

movies as cheaply as possible? It is fine to buy a few additional movies if that leads to a smaller

total cost $($see example below$).$ Each coupon can only be used once.

Design an algorithm which given the set of available coupons, finds the smallest total cost of

buying the $n$ movies. The algorithm must have time complexity polynomial in $n$ and $m,$ assuming

a unit cost analysis $($e$.$g$.,$ you may assume that adding$/$multiplying$/$comparing two numbers

takes $O(1)$ time$).$ The input to the algorithm consists of:

The integers $n,m,$ and $C$ as described above.

For each $1im,$ a pair of integers $(b_i,f_i)($where $1f_i{b}_{i}n),$ indicating that the

$i\text{'}$th coupon says "buy $b_i,$ get $f_i$ for free".