def trip(hotels, allowance):
    """Return a trip plan, staying within an allowance of miles per day.

    A plan is a pair of a total cost (sum of room rates) and a list of hotels.
    Each hotel is a triple of name, distance from the start, and room rate.
    The given list of hotels must be listed in nondecreasing distance.
    The last 'hotel' on the list is actually the ultimate trip destination
    and must be included in any plan; its room rate might be 0.
    All mileages must be integers: hotel distances and the allowance.
    If no plan is feasible, the procedure raises a ValueError."""

    ## You need to write this.


## For each hotel, there is a triple: (name, miles from St. Peter, room rate)
hotels=[('Super 8 Mankato', 10, 47),
        ('Days Inn Mankato', 10, 49),
        ('Microtel Inn & Suites Mankato', 10, 65),
        ('Microtel Inn Clear Lake', 87, 61),
        ('Super 8 Clear Lake', 88, 71),
        ('Super 8 Story City', 149, 48),
        ('Days Inn Ames', 160, 80),
        ('Super 8 Ames', 161, 55),
        ('Microtel Inn & Suites Ames', 161, 54),
        ('Days Inn Ankeny - Des Moines', 180, 54),
        ('Super 8 Ankeny/Des Moines Area', 180, 59),
        ('Days Inn Des Moines/Merle Hay', 185, 64),
        ('Super 8 Urbandale/Des Moines Area', 185, 59),
        ('Ramada Tropics Resort / Conference Center Des Moines', 185, 71),
        ('Microtel Inn & Suites Des Moines Urbandale', 185, 53),
        ('Baymont Inn and Suites Des Moines North', 186, 63),
        ('Travelodge Des Moines IA', 186, 54),
        ('Days Inn Des Moines-West Clive', 188, 37),
        ('Super 8 Clive/W DesMoines', 188, 59),
        ('Days Inn Osceola', 228, 55),
        ('Super 8 Osceola IA', 228, 59),
        ('Super 8 Lamoni', 256, 53),
        ('Super 8 Bethany MO', 281, 51),
        ('Super 8 Cameron', 316, 51),
        ('Super 8 Kearney/KC Area', 343, 51),
        ('Days Inn Liberty/NE Kansas City', 352, 39),
        ('Super 8 Liberty NE Kansas City  Area', 352, 41),
        ('Super 8 KC/Adj. to Worlds of Fun', 357, 42),
        ('Days Inn Kansas City MO Near Worlds of Fun', 357, 32),
        ('Ramada Conference Center Kansas City', 360, 71),
        ('Baymont Inn and Suites Kansas City South', 371, 58),
        ('Super 8 Harrisonville', 392, 51),
        ('Super 8 Butler', 420, 49),
        ('Days Inn Butler', 420, 65),
        ('Super 8 Nevada', 449, 43),
        ('Super 8 Lamar', 472, 54),
        ('Super 8 Carthage', 497, 51),
        ('Days Inn Joplin', 503, 54),
        ('Microtel Inn and Suites Joplin', 504, 47),
        ('Microtel Inn and Suites Miami', 517, 64),
        ('Super 8 - Big Cabin/Vinita Area', 540, 48),
        ('Days Inn and Suites Pryor', 564, 44),
        ('Days Inn Wagoner', 583, 47),
        ('Days Inn Muskogee', 598, 38),
        ('Super 8 Muskogee', 599, 54),
        ('Days Inn and Suites McAlester', 656, 62),
        ('Super 8 McAlester', 658, 55),
        ('Super 8 Kiowa', 671, 53),
        ('Days Inn And Suites Atoka', 696, 63),
        ('Days Inn Durant', 725, 56),
        ('Super 8 Sherman', 754, 51),
        ('Days Inn McKinney', 780, 50),
        ('Super 8 McKinney/Plano Area', 781, 51),
        ('Days Inn Dallas Plano', 794, 34),
        ('Ramada Limited - Plano', 794, 43),
        ('Super 8 Plano/Dallas Area', 794, 42),
        ('Super 8 Richardson Dallas', 800, 51),
        ('Super 8 Dallas', 822, 57),
        ('Super 8 Waxahachie TX', 838, 42),
        ('Super 8 Hillsboro TX', 867, 59),
        ('Knights Inn Waco', 895, 47),
        ('Days Inn Waco', 895, 47),
        ('Super 8 Waco University Area', 900, 42),
        ('Knights Inn Waco South', 901, 42),
        ('Super 8 Waco/Mall area TX', 902, 53),
        ('Days Inn Temple', 931, 52),
        ('Knights Inn Temple', 931, 38),
        ('Temple Travelodge', 933, 40),
        ('Super 8 Temple', 934, 51),
        ('Knights Inn - Belton/Temple', 936, 50),
        ('Wingate by Wyndham Round Rock', 975, 84),
        ('Days Inn and Suites Round Rock', 976, 71),
        ('Ramada Limited - Austin North', 986, 39),
        ('Super 8 Austin North/University Area', 987, 65),
        ('Howard Johnson Austin North', 987, 36),
        ('Days Inn Austin Crossroads', 987, 47),
        ('Baymont Inn & Suites Austin Highland Mall', 988, 62),
        ('Travelodge Austin', 988, 54),
        ('Ramada - Austin Central', 988, 72),
        ('Super 8 Austin University/Downtown Area', 989, 72),
        ('Super 8 Austin/Airport North', 990, 102),
        ('Days Inn Austin/University/Downtown', 991, 51),
        ('Super 8 Austin/Dtwn/Capitol Area', 992, 60),
        ('Trip destination in South Austin', 996, 0)]