Anna has just won a contest that allows her to take n pieces of candy out of a candy store for free. Anna is old enough to realize that some candy is expensive, while other candy is relatively cheap,...

Anna has just won a contest that allows her to take
n
pieces of candy out

of a candy store for free. Anna is old enough to realize that some candy is

expensive, while other candy is relatively cheap, costing much less. The

jars of candy are numbered 0, 1, . . .,
m−1, so that jar
j
has
nj
pieces in

it, with a price of
cj
per piece. Design an
O(n+m)-time algorithm that

allows Anna to maximize the value of the pieces of candy she takes for

her winnings. Show that your algorithm produces the maximum value for

Anna.