Закупка с приоритетом
Для ремонта нужно закупить товары двух типов: P и T. В магазине есть товаров, для каждого известны цена и тип; каждый товар можно купить не более одного раза. На покупку выделено рублей.
Необходимо купить как можно больше товаров независимо от их типа. Если это можно сделать несколькими способами, выбирают способ, при котором куплено как можно больше товаров типа P. Если и таких способов несколько, выбирают тот, при котором останется как можно больше денег.
Определите количество купленных товаров типа P и сумму, которая останется после покупки.
Входные данные
В первой строке находятся два натуральных числа: — количество товаров () и — сумма, выделенная на покупку (). Каждая из следующих строк содержит цену товара (натуральное число, не превышающее ) и его тип — заглавную латинскую букву P или T.
Товары идут в произвольном порядке; товары одного типа с одинаковой ценой возможны. Гарантируется, что хотя бы один товар купить можно.
Выходные данные
Выведите два целых числа: сначала количество купленных товаров типа P, затем сумму, которая останется после покупки.
Примеры
4 8 3 P 2 T 3 P 2 T
2 0
4 7 5 P 2 T 2 T 2 T
0 1
Примечание
В первом примере можно купить три товара. Покупка двух товаров типа P по 3 и одного товара типа T за 2 предпочтительнее покупки одного товара типа P и двух товаров типа T, хотя денег при этом не остаётся. Во втором примере можно купить три товара типа T; вместе с товаром типа P удалось бы купить только два товара.