Fit a chat into the context window

A chat application must fit the instructions and as much recent conversation as possible into the model's context window. Decide what to keep.

What to build

A program that keeps the instructions and the most recent messages that fit within a token budget.

Requirements

  • Each message is ROLE TEXT; its token count is the number of words in TEXT.
  • Always keep the first message. Then, from the newest message backwards, keep each message that still fits in the budget, stopping at the first that does not (so the kept history has no gaps).
  • Print the kept messages in order as ROLE: TEXT, then tokens used T of MAX.

Input

Line 1: the maximum number of tokens. Line 2: n. Then n messages.

Output

The kept messages, then the token line.

Constraints

1 ≤ n ≤ 1000; the first message always fits.

Example

Input:

15
4
system You are a helpful tutor
user What is a token
assistant A piece of text
user How long is a context window

Output:

system: You are a helpful tutor
assistant: A piece of text
user: How long is a context window
tokens used 15 of 15

Why it works

The newest messages matter most for the next reply and the instructions must never be lost; stopping at the first message that does not fit keeps the remembered conversation continuous.

Examples

Example 1 · Input
15
4
system You are a helpful tutor
user What is a token
assistant A piece of text
user How long is a context window
Expected output
system: You are a helpful tutor
assistant: A piece of text
user: How long is a context window
tokens used 15 of 15
Example 2 · Input
3
2
system Be brief
user hi
Expected output
system: Be brief
user: hi
tokens used 3 of 3

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

The first message (the instructions) is always kept; count tokens as words of the message text.

Hint 2

Walk from the newest message backwards, keeping messages while they fit in the remaining budget; stop at the first that does not fit.

Hint 3

Print the kept messages in their original order.

Solution

Show one correct solution (try it yourself first)
limit = int(input())
n = int(input())
messages = [input().split(maxsplit=1) for _ in range(n)]
used = len(messages[0][1].split())
kept = []
for role, text in reversed(messages[1:]):
    size = len(text.split())
    if used + size > limit:
        break
    used += size
    kept.append((role, text))
for role, text in [messages[0]] + kept[::-1]:
    print(f"{role}: {text}")
print(f"tokens used {used} of {limit}")

Lesson: Tokens and context windows →