UVa 11034 - Ferry Loading IV

# UVa 11034 - Ferry Loading IV

number_of_test_cases = int(input())
for test_case in range(1, number_of_test_cases+1):

    ferry_length, number_of_cars = map(int, input().split())
    ferry_length = ferry_length * 100

    available_space = {'left': ferry_length, 'right':ferry_length}
    number_of_trips_to_serve = {'left': 0, 'right': 0}

    for i in range(number_of_cars):
        car = input().split()
        car_length = int(car[0])
        bank = car[1]

        if available_space[bank] >= car_length:
            available_space[bank] = available_space[bank] - car_length
        else:
            number_of_trips_to_serve[bank] = number_of_trips_to_serve[bank] + 1
            available_space[bank] = ferry_length - car_length

    for bank in ['left', 'right']:
        if available_space[bank] < ferry_length:
            number_of_trips_to_serve[bank] = number_of_trips_to_serve[bank] + 1

    number_of_trips_required = max( number_of_trips_to_serve['left']*2-1  , number_of_trips_to_serve['right']*2 )

    print(f'{number_of_trips_required}' )