Dish Selection Challenge

Problem Description

You are given a list of n dishes, their corresponding vote counts, and their names. Your task is to select exactly k dishes that have received the highest votes. In the case where multiple dishes have the same vote count, the dish with the lexicographically smaller name is preferred.

After selecting the top k dishes based on votes (using the rule above), output the names of these dishes sorted in lexicographical order.

Formally, let \(V = [v_1, v_2, \dots, v_n]\) be the vote counts and \(N = [n_1, n_2, \dots, n_n]\) be the dish names. First, choose a subset \(S\) of \(k\) indices such that the votes \(\{ v_i : i \in S \}\) are maximized. If there exists more than one such subset, choose the one for which the corresponding dish names (when sorted lexicographically) form the lexicographically smallest sequence. Finally, print the selected dish names in lexicographical order.

inputFormat

The input is read from standard input (stdin) in the following format:

1. The first line contains two space-separated integers: n (the number of dishes) and k (the number of dishes to select).
2. The second line contains n space-separated integers representing the vote counts for each dish.
3. The third line contains n space-separated strings representing the names of the dishes.

outputFormat

Output a single line to standard output (stdout) containing the selected k dish names in lexicographical order, separated by a single space.

5 3
4 2 3 6 1
pasta curry salad burger fries

burger pasta salad