Closest Meal Plan

You are given a list of available meals. Each meal has a name and an associated calorie count. Your task is to choose exactly n meals such that the sum of their calorie counts is as close as possible to a target value \(C\).

Mathematically, if the chosen meals have calorie counts \(c_1, c_2, \dots, c_n\), you need to minimize \(|\sum_{i=1}^{n} c_i - C|\).

It is guaranteed that there is at least one valid combination. In the case of multiple optimal solutions, you may output any one of them.

inputFormat

The first line of input contains three integers m, n, and C, where m is the number of available meals, n is the number of meals to select, and C is the target calorie count. The next m lines each contain a meal description with the meal name and its calorie count separated by a space. Note that the meal name may contain spaces.

outputFormat

Output exactly n lines. Each line should contain the name of the meal and its calorie count separated by a space. The selected combination must have a total calorie sum as close as possible to C. If there are multiple valid answers, any one is accepted.## sample

5 3 1500
Chicken Salad 400
Steak 700
Pasta 600
Burger 900
Tacos 300

Chicken Salad 400
Steak 700
Tacos 300