Сговор с экзаменатором

Time limit = 2 second(s)

Memory limit = 64 Mb

Дело в том, что ректор приказал экзаменатору отчислить K студентов, чтобы освободить нужное количество мест в общежитии. Но экзаменатор не хочет ставить «неуд.» кому попало, и он попросил Вас написать программу, которая поможет ему в выборе «жертв».

Экзаменатор хочет минимизировать суммарный уровень знаний всех отчисленных студентов. При этом после отчисления очередного студента он расстраивается и просто не может отчислить следующих M студентов. Ну и наконец, Вас он также не может отчислить, ведь у вас договоренность! В лицо Вас экзаменатор не знает. Вы договорились, что он просто не будет отчислять студентов, которых зовут «Mishik».

Input Первая строка входа содержит общее количество студентов N, 0 < N ≤ 1000, количество студентов, подлежащих отчислению K, 0 ≤ K ≤ 1000, и количество студентов, которых нельзя отчислять после только что отчисленного студента M, 0 ≤ M ≤ 1000.

Далее следуют N строк — список студентов в порядке их появления у экзаменатора. Каждая строка содержит имя студента (строка из не более чем 20 символов английского алфавита или цифр) и уровень его знаний (целое число из диапазона [0,  5], разделенные пробелом.

Output Выведите минимально возможный суммарный уровень знаний отчисленных студентов, либо Impossible, если отчислить K студентов невозможно.

4 2 1
Igor 5
Mishik 0
Dan 4
Artem 3

8

Author:
Игорь Квасов, индивидуальное первенство МФТИ по программированию, 21 сентября 2008 года
20 сентября 2008

<PREV | Problem set | Search related messages | NEXT>