Suppose a friend of yours has created a simulation game based on J.R.R. Tolkien’s epic The Lord of the Rings. The game environment is Middle Earth, which is populated by various noble creatures, including hobbits, humans, dwarves, and elves. Unfortunately, these noble creatures are under attack and need to get to safe havens, known as “strongholds.” Some strongholds are larger than others, of course, and each stronghold, s, can only hold some number, N_s, of these creatures. Initially, let us assume each stronghold is empty, and the noble creatures are living in various regions, with each region, r, containing some number, N_r, of noble creatures. Moreover, we know, for each region, r, the set of strongholds, S_r, that can be reached from r in at most three days’ travel. Your job is to figure out how to move the maximum number of noble creatures possible from the regions where they currently live to the various strongholds in three days’ time while not overcrowding any stronghold. Describe and analyze an efficient algorithm to solve this game.