An ad server gathers candidate ads for a request and scores them. The same ad often arrives through several paths, each carrying a different score, so duplicates are mixed into the candidate set.

Implement top_k(items, k), which picks the top k from these candidates.

Input

items = [("A", 0.8), ("B", 0.9), ("C", 0.9), ("D", 0.7)]
k = 3

• Each entry is an (item id, score) pair.
• Scores are floats and may be negative.
• The same id may appear several times with different scores.
• k is an integer and may be zero or negative.

Output

Return the top k as a list of (id, score) tuples.

top_k(items, 3)
# [("B", 0.9), ("C", 0.9), ("A", 0.8)]

Building it takes four steps.

1. Collapse duplicate ids. This input has none, so all four survive.
2. Line them up by score descending: two at 0.9 (B, C), then 0.8 (A), then 0.7 (D).
3. Break the tie between B and C by id ascending. B comes before C.
4. Slice the first three. B, C and A remain; D is cut.

Handling duplicate ids

When an id appears several times, keep only its highest score — the maximum, not the one that appeared last.

In [("A", 0.1), ("A", 0.9), ("A", 0.5), ("B", 0.8)], A appears three times and its best score is 0.9. After collapsing there is one A at 0.9 and one B at 0.8, so k=2 gives [("A", 0.9), ("B", 0.8)].

Skip this step and the same id ends up in the result twice.

Things to watch

1. If k exceeds the candidate count, return as many as exist. This is not an error. With a single candidate and k=10, that one candidate comes back.
2. If k is zero or negative, return an empty list. In Python ranked[:-3] is not an empty list but the list minus its last three items, so passing a negative k straight into a slice gives the wrong answer.
3. Negative scores are sorted like any other. -0.1 ranks above -0.5.
4. If every score is equal, the result is simply id ascending.
5. Empty input returns an empty list.

Implement top_k(items, k). Return a list of (id, score) tuples.