PPaste!

import sys
import itertools
from bisect import bisect_right


def parse_input():
    """
    Returns a couple: the objective calories and a list of
    restaurants (name, calories)
    """
    objective = int(sys.stdin.readline())
    restaurants = []
    for line in sys.stdin.readlines():
        name, cal = (x.strip('" \n') for x in line.split('='))
        cal = int(cal)
        restaurants.append((name, cal))
    return objective, restaurants


def naive_create_schedule(objective, restaurants, days=5):
    """
    Returns the schedule: the calories that we will eat this week and the
    list of restaurants that are the closest to our objective
    """
    assert(days <= len(restaurants))

    sol_value = 0
    sol_names = []
    for restaurants in itertools.combinations(restaurants, days):
        calories = sum(restaurant[1] for restaurant in restaurants)
        if abs(objective - calories) < abs(objective - sol_value):
            sol_value = calories
            sol_names = [restaurant[0] for restaurant in restaurants]

    return sol_value, sol_names


def fast_create_schedule(objective, restaurants, days=5):
    """
    Returns the schedule: the calories that we will eat this week and the
    list of restaurants

    Greedy: We pick the restaurant that is close to the per-day calories we
    need to eat
    """
    # We sort the restaurants list to use binary search and keep track of the
    # old indexes
    restaurants_cal = sorted(
        [(restaurant[1], i) for i, restaurant in enumerate(restaurants)]
    )

    sol_value = 0
    sol_names = []

    for i in range(days):
        mean = objective / (days - i)

        # Find the closest restaurant to the mean
        # (rightmost value less than or equal to)
        j = bisect_right(restaurants_cal, (mean, 0)) - 1
        cal, index = restaurants_cal[j]

        sol_value += cal
        sol_names.append(restaurants[index][0])

        objective -= cal
        del restaurants_cal[j]

    return sol_value, sol_names


if __name__ == '__main__':
    cal, restaurants = parse_input()
    print(fast_create_schedule(cal, restaurants, days=5))
    print(naive_create_schedule(cal, restaurants, days=5))