Problem Description

Sick and tired of pushing paper in the dreary bleary-eyed world of finance, Flo ditched her desk job and built her own restaurant.

In the small restaurant, there are several two-seat tables, four-seat tables and six-seat tables. A single diner or a group of two diners should be arranged to a two-seat table, a group of three or four diners should be arranged to a four-seat table, and a group of five or six diners should be arranged to a six-seat table.

Flo’s restaurant serves delicious food, and many people like to eat here. Every day when lunch time comes, the restaurant is usually full of diners. If there is no suitable table for a new coming group of diners, they have to wait until some suitable table is free and there isn’t an earlier arrival group waiting for the same kind of tables. Kind Flo will tell them how long they will get their seat, and if it’s longer than half an hour, they will leave for another restaurant.

Now given the list of coming diners in a day, please calculate how many diners take their food in Flo’s restaurant. You may assume it takes half an hour for every diner from taking a seat to leaving the restaurant.

Input

There are several test cases. The first line of each case contains there positive integers separated by blanks, A, B and C (A, B, C >0, A + B + C <= 100), which are the number of two-seat tables, the number of four-seat tables and the number of six-seat tables respectively. From the second line, there is a list of coming groups of diners, each line of which contains two integers, T and N (0 < N <= 6), representing the arrival time and the number of diners of each group. The arrival time T is denoted by HH:MM, and fixed between 08:00 and 22:00 (the restaurant closes at 23:00). The list is sorted by the arrival time of each group in an ascending order, and you may assume that no groups arrive at the same time. Each test case is ended by a line of “#”.

A test case with A = B = C = 0 ends the input, and should not be processed.

Output

For each test case, you should output an integer, the total number of diners who take their food in Flo’s restaurant, in a separated line.

Sample Input

1 1 1
10:40 1
10:50 2
11:00 4
#
1 1 1
10:40 1
10:50 2
11:00 2
#
1 2 1
10:30 1
10:40 3
10:50 2
11:00 1
11:20 5
#
0 0 0

Sample Output

7
3
12

题目大意

输入三个数x,y,z,分别表示可以坐2,4,6个人的座位的个数。当x,y,z,都等于0时结束。接下输入食客到达餐馆的时间和人数，并且1~2人只能坐2人座，3~4人只能坐4人座，5~6人只能坐6人座，每桌食客用餐时间均为30分钟，并且每位食客在没位置时可以等待的时间<=30分钟，超过则会离开这家餐馆。计算在这家餐馆就餐的人最多是？

c++

#include<iostream>
#include<queue> //队列头文件
#include<cstring>
using namespace std;
struct sj
{
    char a[50];
    int b,c;
};
int main()
{
    queue<int>a;     //定义队列
    queue<int>n;
    queue<int>o;
    sj m[1000];
    int b,c,d,e,f,g,h;
    while(1)
    {
        cin>>b>>c>>d;
        if(d==0&&b==0&&c==0)
            break;
        while(!a.empty())    //将队列清空
            a.pop();
        while(!n.empty())
            n.pop();
        while(!o.empty())
            o.pop();
        e=0;
        while(1)
        {
            cin>>m[e].a;
            if(strcmp(m[e].a,"#")==0)
                break;
            cin>>m[e].b;
            m[e].c=((m[e].a[0]-'0')*10+(m[e].a[1]-'0'))*60+(m[e].a[3]-'0')*10+(m[e].a[4]-'0');     //用来存放食客到达餐馆的时间
            e++;
        }
        g=0;
        for(int i=0;i<e;i++)
        {
            if(m[i].b<=2)      //判断食客的人数向其安排合适座位
            {
                if(b>0)        //当还有空位时直接将食客就餐结束时间入队座位-1加上人数
                {
                    a.push(m[i].c+30);
                    b--;
                    g=g+m[i].b;
                }
                else
                {
                    if(m[i].c+30>=a.front())   //当无座位时比较刚进餐馆的食客能否在30分钟内等到空位
                    {
                        h=a.front();
                        a.pop();
                        if(m[i].c<h)
                            a.push(h+30);
                        else
                            a.push(m[i].c+30);
                        g=g+m[i].b;
                    }
                }
            }
            else if(m[i].b<=4)    //同上
            {
                if(c>0)
                {
                    n.push(m[i].c+30);
                    c--;
                    g=g+m[i].b;
                }
                else
                {
                    if(m[i].c+30>=n.front())
                    {
                        h=n.front();
                        n.pop();
                        if(m[i].c<h)
                            n.push(h+30);
                        else
                            n.push(m[i].c+30);
                        g=g+m[i].b;
                    }
                }
            }
            else if(m[i].b<=6)     //同上
            {
                if(d>0)
                {
                    o.push(m[i].c+30);
                    d--;
                    g=g+m[i].b;
                }
                else
                {
                    if(m[i].c+30>=o.front())
                    {
                        h=o.front();
                        o.pop();
                        if(m[i].c<h)
                            o.push(h+30);
                        else
                            o.push(m[i].c+30);
                        g=g+m[i].b;
                    }
                }
            }
        }
        cout<<g<<endl;
    }
    return 0;
}