Qurban 2011
Курбан — это исламская практика, включающая жертвоприношение определенного скота. Курбан проводится только с 10 по 13 Зульхиджа, последнего месяца исламского календаря. Для жертвоприношения подходят верблюды, крупный рогатый скот, буйволы, овцы и козы. Мясо каждого забитого верблюда, крупного рогатого скота или буйвола можно разделить на 7 равных частей для распределения между 7 людьми. Поскольку козы и овцы меньше, одна коза или овца эквивалентна одной части от предыдущих трех видов скота. Человек может зарегистрироваться на жертвоприношение более чем одной части.
Чтобы правильно рассчитать количество скота для забоя, необходимо убедиться, что все 7 частей учтены для забоя одного буйвола. В противном случае ответственность за стоимость ложится на ответственного человека. Если человек регистрируется на более чем 7 частей, например, на 8 частей буйвола, оставшаяся часть должна быть объединена с частями, жертвованными другими людьми.
Обычно буйволы и овцы поставляются фермером, а место для забоя выбирается в зависимости от клиентов. Есть только один грузовик, который может перевозить либо буйволов, либо овец. Грузовик может перевозить максимум 3 буйвола или 6 овец за один раз.
Дано несколько заказов на курбан, рассчитайте минимальное количество поездок для транспортировки буйволов и овец для забоя.
Входные данные
Входные данные состоят из нескольких строк. Первая строка — это целое число T, представляющее количество тестовых данных. За ним следуют T строк данных. Каждая из этих строк начинается с целого числа m, представляющего количество заказов, за которым следует один пробел и набор заказов. Заказы имеют следующий формат: два символа, где первый — это либо 'b' (представляет части буйвола), либо 's' (представляет овцу). За этим следует целое число, представляющее количество заказов на соответствующие части коровы или овцы. Каждый заказ разделяется одним пробелом.
Выходные данные
Выходные данные — это минимальное количество поездок для транспортировки буйволов и овец для забоя.