Вася играет в Need For Brake. Играет потому, что ему подарили на день рождения новенький компьютерный руль! Теперь то он уж точно займет первое место в чемпионате в его любимой компьютерной игре в жанре авто-симуляторов!
В чемпионате, состоящем из некоторого количества заездов, принимают участие n гонщиков. По результатам каждого заезда гонщики занимают места с 1 по n-ое (никакие два гонщика не разделяют одно место) и первые m мест являются призовыми. За i-ое призовое место гонщик получает bi очков, которые прибавляются к его очкам, заработанным за все предыдущие заезды. Известно, что к данному моменту гонщик i набрал ai очков. По итогам чемпионата гонщики сортируются в порядке убывания суммы очков. При равном количестве очков сортировка производится по возрастанию имени гонщика в лексикографическом порядке.
К сожалению, чемпионат уже подошел к концу и остался всего лишь один заезд. Вася решил узнать какое самое высокое и самое низкое место он может занять по итогам чемпионата.
Выходные данные
Вывести два числа — самое высокое и самое низкое места, которые может занять Вася по итогам чемпионата.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
teama 10
teamb 20
teamc 40
2
10 20
teama
|
2 3
|
|
2
|
2
teama 10
teamb 10
2
10 10
teamb
|
2 2
|