Fit the History in the Budget in Python

Interview question: “A chat with your bot keeps growing, but the model accepts only so many tokens. Which messages do you send?” The usual answer: always send the system message, then as many of the newest messages as fit the token budget, dropping the oldest first.

Walk the history backward, from the newest message. Add each message's cost to what you've used, and at the first message that doesn't fit, stop. Never send half a message, and never skip one to keep an older one: that would leave a hole in the conversation. In this lesson, one word counts as one token.

For example, take a budget of 20, a system message of 5 words and three messages of 6, 9 and 4 words, oldest first. You send the system message and the two newest messages, in their original order:

used = 5                          (the system message)
newest, 4 words:   5 + 4 = 9      fits, keep
next, 9 words:     9 + 9 = 18     fits, keep
oldest, 6 words:   18 + 6 = 24    over 20, stop

The starting code has an 11-word system message, a 5-message chat about a teapot order and BUDGET = 40. Finished, the script prints the messages it kept (the check also tries a budget of 100, which keeps all 5, and 15, which keeps none):

user: Is the teapot safe for the dishwasher?
assistant: Yes, but wash the lid by hand.
user: Can you ship a matching mug to Canada?
Kept 3 of 5 messages

Your task: in fit_history, start used at the system message's tokens, walk reversed(messages), put each message that fits at the front of kept and add its cost to used, and break at the first message that doesn't fit.

Assignment
Follow the Coding Tutorial to write the loop in fit_history that keeps the newest messages within the budget.

Hint
Walking newest first, each kept message goes in front: kept.insert(0, message). Use break, not continue: after skipping message 2, message 1 (7 words) would still fit and leave a hole.