Suppose the football coach for the Anteaters has heard about your abilities to solve challenging problems and has hired you to write a computer program that can decide which of their many trophies to feature on their prized trophy shelf. He is asking that you do this as a computer program, rather than just coming up with a single decision, because the Anteaters are getting new trophies every year. The trophies come in all different shapes and sizes, and the ones on the prized trophy shelf have to be lined up next to one another. So the dimension that matters most is a trophy’s width in centimeters, which is given as an integer. In addition, the coach has assigned an integer score to each trophy, so that a very prestigious trophy, like the one for winning the championship, would have a high score, whereas a less prestigious trophy, like the one for having the funniest uniforms, would have a low score. Moreover, given his eccentric nature, these scores can be arbitrarily large. He has asked that, given a listing of all the team’s trophies along with their widths and prestige scores, your program should choose the set that maximizes the total prestige score and fits on the team’s trophy shelf. Show that the decision version of the problem the coach has given you is NPcomplete.