Нелегка студенческая жизнь. На собственном опыте пришлось прочувствовать это некоторым студентам Берляндского университета. За два года обучения возникла у них стойкая неприязнь к заведующей одной из кафедр. В самом деле, то группы переформирует, то запретит ставить студентам автоматы, то совершит еще какой-нибудь отвратительный поступок. Решили студенты, что все это не должно сойти заведующей с рук...

Благодаря связям в ректорате студентам стало известно, что на следующем заседании ректората будет рассмотрено n приказов, касающихся заведующей, при этом принято из них будет ровно p. Для каждого приказа определено две величины: a_i — количество седых волос, которое прибавится на голове у заведующей, если она выполнит этот приказ, и b_i — недовольство ректората тем, что данный приказ не будет выполнен. Студенты могут добиться того, чтобы в ректорате были приняты любые выбранные ими p приказов. Студенты знают, что из числа этих p приказов заведующая выполнит ровно k, причем она будет выбирать их таким образом, чтобы минимизировать в первую очередь суммарное недовольство ректората ее действиями, а во вторую — количество седых волос, которое прибавится у нее на голове.

Студенты хотят выбрать p приказов так, чтобы на голове у заведующей прибавилось как можно больше седых волос. Если при этом есть несколько вариантов принятия приказов, то в интересах студентов максимизировать недовольство ректората действиями заведующей. Помогите им.