시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 18 2 2 50.000%

문제

프로그래밍 대회가 끝난 연정이는 파티를 열기로 결정했다. 그래서 친구들을 초대하여 소주와 맥주를 부어라 마셔라하며 즐겁게 하루를 보냈다. 

파티가 끝난 지금 연정이는 친구들을 안전하게 자신의 집으로 돌아가기를 원한다. 문제는 이들의 집은 너무 멀어 반드시 차를 이용해야한다는 것이다. 

자동차를 이용하기 위해선 아래의 조건은 반드시 만족해야한다.

  • 해당 지역으로 이동하는 자동차에는 반드시 술에 취하지 않은 사람이 의무적으로 한 명 탑승 ( 운전을 해야하므로 ) 하며 해당 지역 이외로는 가지 않는다.
  • 자동차에 빈 자리가 남을 수는 있으나 초과하여 태울 수는 없다.

연정이 집에 놀러온 친구들과 각 지역으로 갈 수 있는 자동차 개수 및 지역 개수가 주어질 때 자동차 자리가 모자라서 또는 집으로 이동 할 자동차가 없어 

어쩔 수 없이 연정이 집에서 자야하는 사람이 몇 명인지 알아내시오.

입력

첫 줄에는 전체 테스트 개수 ( K ) 가 주어진다. ( K ≥ 1 )

다음 줄 부터는 전체 테스트 개수만큼 아래와 같은 형식이 주어진다.

연정이 집에 놀러온 친구 수 ( n ) , 다른 지역으로 이동할 수 있는 자동차 수 ( c ) ,  지역의 수 ( ℓ ) [ n ≤ 500 , c ≤ n , ℓ ≤ c ]

하위 n 개 줄은 각 친구가 사는 지역 번호 [ 지역번호는 1 부터 ℓ 까지 ] 와 취했는지 ( I ) 안 취했는지 ( S ) 를 나타내는 문자로 구성된다.

그 다음 하위 c 개 줄은 이동할 지역 번호 [ 지역번호는 1 부터 ℓ 까지 ] 와 탑승할 수 있는 최대 좌석 개수 ( 2 ~ 8 ) 가 주어진다.

출력

각 테스트에서 연정이 집에서 자야하는 친구의 수를 "Data Set x:" ( "" 제외 ) 형식과 함께 출력하시오.

예제 입력 1

1
8 3 2
1 I
1 I
1 S
2 I
1 I
1 I
2 S
2 S
1 3
1 3
2 4

예제 출력 1

Data Set 1:
2
W3sicHJvYmxlbV9pZCI6IjUxODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMGNcdWQyZjBcdWI5N2MgXHVjNWY0XHVjNWI0XHViNzdjISEhIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHViMzAwXHVkNjhjXHVhYzAwIFx1YjA1ZFx1YjA5YyBcdWM1ZjBcdWM4MTVcdWM3NzRcdWIyOTQgXHVkMzBjXHVkMmYwXHViOTdjIFx1YzVmNFx1YWUzMFx1Yjg1YyBcdWFjYjBcdWM4MTVcdWQ1ODhcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyZuYnNwO1x1Y2U1Y1x1YWQ2Y1x1YjRlNFx1Yzc0NCBcdWNkMDhcdWIzMDBcdWQ1NThcdWM1ZWMgXHVjMThjXHVjOGZjXHVjNjQwIFx1YjllNVx1YzhmY1x1Yjk3YyBcdWJkODBcdWM1YjRcdWI3N2MgXHViOWM4XHVjMTU0XHViNzdjXHVkNTU4XHViYTcwIFx1Yzk5MFx1YWM4MVx1YWM4YyBcdWQ1NThcdWI4ZThcdWI5N2MgXHViY2Y0XHViMGM4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWQzMGNcdWQyZjBcdWFjMDAgXHViMDVkXHViMDljJm5ic3A7XHVjOWMwXHVhZTA4Jm5ic3A7XHVjNWYwXHVjODE1XHVjNzc0XHViMjk0IFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1Yzc0NCBcdWM1NDhcdWM4MDRcdWQ1NThcdWFjOGMgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzlkMVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWFjMDBcdWFlMzBcdWI5N2MgXHVjNmQwXHVkNTVjXHViMmU0LiBcdWJiMzhcdWM4MWNcdWIyOTQgXHVjNzc0XHViNGU0XHVjNzU4IFx1YzlkMVx1Yzc0MCBcdWIxMDhcdWJiMzQgXHViYTQwXHVjNWI0Jm5ic3A7XHViYzE4XHViNGRjXHVjMmRjIFx1Y2MyOFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWM1N2NcdWQ1NWNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM3OTBcdWIzZDlcdWNjMjhcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzEyMCBcdWM1NDRcdWI3OThcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQwIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWM1N2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVkNTc0XHViMmY5IFx1YzljMFx1YzVlZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVjNzkwXHViM2Q5XHVjYzI4XHVjNWQwXHViMjk0IFx1YmMxOFx1YjRkY1x1YzJkYyBcdWMyMjBcdWM1ZDAgXHVjZGU4XHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNzU4XHViYjM0XHVjODAxXHVjNzNjXHViODVjIFx1ZDU1YyBcdWJhODUgXHVkMGQxXHVjMmI5ICgmbmJzcDtcdWM2YjRcdWM4MDRcdWM3NDQgXHVkNTc0XHVjNTdjXHVkNTU4XHViYmMwXHViODVjICkgXHVkNTU4XHViYTcwIFx1ZDU3NFx1YjJmOSBcdWM5YzBcdWM1ZWQgXHVjNzc0XHVjNjc4XHViODVjXHViMjk0IFx1YWMwMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1Yzc5MFx1YjNkOVx1Y2MyOFx1YzVkMCBcdWJlNDggXHVjNzkwXHViOWFjXHVhYzAwIFx1YjBhOFx1Yzc0NCBcdWMyMThcdWIyOTQgXHVjNzg4XHVjNzNjXHViMDk4IFx1Y2QwOFx1YWNmY1x1ZDU1OFx1YzVlYyBcdWQwZGNcdWM2YjggXHVjMjE4XHViMjk0IFx1YzVjNlx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM1ZjBcdWM4MTVcdWM3NzQmbmJzcDtcdWM5ZDFcdWM1ZDAgXHViMTgwXHViN2VjXHVjNjI4IFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1YWNmYyZuYnNwO1x1YWMwMSBcdWM5YzBcdWM1ZWRcdWM3M2NcdWI4NWMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzkwXHViM2Q5XHVjYzI4IFx1YWMxY1x1YzIxOCBcdWJjMGYgXHVjOWMwXHVjNWVkIFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjIFx1Yzc5MFx1YjNkOVx1Y2MyOCBcdWM3OTBcdWI5YWNcdWFjMDAgXHViYWE4XHVjNzkwXHViNzdjXHVjMTFjIFx1YjYxMFx1YjI5NCBcdWM5ZDFcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5IFx1ZDU2MCBcdWM3OTBcdWIzZDlcdWNjMjhcdWFjMDAgXHVjNWM2XHVjNWI0Jm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzViNFx1Y2E1NCBcdWMyMTggXHVjNWM2XHVjNzc0IFx1YzVmMFx1YzgxNVx1Yzc3NCZuYnNwO1x1YzlkMVx1YzVkMFx1YzExYyBcdWM3OTBcdWM1N2NcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzc0IFx1YmE4NyBcdWJhODVcdWM3NzhcdWM5YzAgXHVjNTRjXHVjNTQ0XHViMGI0XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MDRcdWNjYjQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1YWMxY1x1YzIxOCAoIEsmbmJzcDspJm5ic3A7XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCZuYnNwO0sgJmdlOyAxJm5ic3A7KTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0IFx1YmQ4MFx1ZDEzMFx1YjI5NCBcdWM4MDRcdWNjYjQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1YWMxY1x1YzIxOFx1YjljY1x1ZDA3YyBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVmMFx1YzgxNVx1Yzc3NCZuYnNwO1x1YzlkMVx1YzVkMCBcdWIxODBcdWI3ZWNcdWM2MjggXHVjZTVjXHVhZDZjIFx1YzIxOCAoIG4gKSAsIFx1YjJlNFx1Yjk3OCBcdWM5YzBcdWM1ZWRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzkwXHViM2Q5XHVjYzI4IFx1YzIxOCAoIGMgKSAsICZuYnNwO1x1YzljMFx1YzVlZFx1Yzc1OCZuYnNwO1x1YzIxOCAoIFx1MjExMyZuYnNwOykmbmJzcDtbJm5ic3A7biAmbGU7IDUwMCAsJm5ic3A7YyAmbGU7IG4gLCZuYnNwO1x1MjExMyAmbGU7IGMgXTxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWM3MDQgbiBcdWFjMWMgXHVjOTA0XHVjNzQwIFx1YWMwMSZuYnNwO1x1Y2U1Y1x1YWQ2Y1x1YWMwMCBcdWMwYWNcdWIyOTQgXHVjOWMwXHVjNWVkJm5ic3A7XHViYzg4XHVkNjM4Jm5ic3A7WyBcdWM5YzBcdWM1ZWRcdWJjODhcdWQ2MzhcdWIyOTQgMSBcdWJkODBcdWQxMzAmbmJzcDtcdTIxMTMgXHVhZTRjXHVjOWMwIF0mbmJzcDtcdWM2NDAgXHVjZGU4XHVkNTg4XHViMjk0XHVjOWMwICggSSZuYnNwOykgXHVjNTQ4IFx1Y2RlOFx1ZDU4OFx1YjI5NFx1YzljMCAoIFMgKSZuYnNwO1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViYjM4XHVjNzkwXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWQ1NThcdWM3MDQgYyBcdWFjMWMgXHVjOTA0XHVjNzQwIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWM5YzBcdWM1ZWQgXHViYzg4XHVkNjM4Jm5ic3A7WyBcdWM5YzBcdWM1ZWRcdWJjODhcdWQ2MzhcdWIyOTQgMSBcdWJkODBcdWQxMzAmbmJzcDtcdTIxMTMgXHVhZTRjXHVjOWMwIF0mbmJzcDtcdWM2NDAgXHVkMGQxXHVjMmI5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1Yzg4Y1x1YzExZCBcdWFjMWNcdWMyMTggKCAyIH4gOCApJm5ic3A7XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjNWQwXHVjMTFjIFx1YzVmMFx1YzgxNVx1Yzc3NCZuYnNwO1x1YzlkMVx1YzVkMFx1YzExYyBcdWM3OTBcdWM1N2NcdWQ1NThcdWIyOTQgXHVjZTVjXHVhZDZjXHVjNzU4IFx1YzIxOFx1Yjk3YyAmcXVvdDtEYXRhIFNldCB4OiZxdW90OyAoICZxdW90OyZxdW90OyBcdWM4MWNcdWM2NzggKSBcdWQ2MTVcdWMyZGRcdWFjZmMgXHVkNTY4XHVhZWQ4IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1MTg2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGFydHkhIiwiZGVzY3JpcHRpb24iOiI8cD5IYXZpbmcgcGFzc2VkIGFsbCBvZiB5b3VyIGV4YW1zIChkZXNwaXRlIHNwZW5kaW5nIGFuIGVudGlyZSBTYXR1cmRheSBhZnRlcm5vb24gYXQgYSBwcm9ncmFtbWluZyBjb250ZXN0LCBubyBsZXNzKSwgeW91IGRlY2lkZSB0byB0aHJvdyBhIGxpdHRsZSBwYXJ0eSwgYW5kIGludml0ZSB5b3VyIDUwMCBvciBzbyBiZXN0IGZyaWVuZHMuIE5hdHVyYWxseSwgdGhlIGJldmVyYWdlcyBhcmUgbm90IHJlc3RyaWN0ZWQgdG8gc295IG1pbGsgYW5kIHNvZGEgd2F0ZXIuIE9uY2UgdGhlIHBhcnR5IGRyYXdzIHRvIGEgY2xvc2UsIGJlaW5nIHRoZSByZXNwb25zaWJsZSBob3N0LCB5b3Ugd2FudCB0byBlbnN1cmUgdGhhdCBldmVyeW9uZSB3aWxsIG1ha2UgaXQgaG9tZSBzYWZlbHkuIEluIHBhcnRpY3VsYXIsIHRoaXMgaW52b2x2ZXMga2VlcGluZyBhbnlvbmUgZnJvbSBkcml2aW5nIGludG94aWNhdGVkLiBZb3UgbWlnaHQgZW5kIHVwIHdpdGggYSBmZXcgcGVvcGxlIHNsZWVwaW5nIGluIHlvdXIgbGl2aW5nIHJvb20gYXMgYSByZXN1bHQuPFwvcD5cclxuXHJcbjxwPldlIGFzc3VtZSB0aGF0IHNvbWUgb2YgeW91ciBmcmllbmRzIGFyZSBjb21pbmcgZnJvbSB0aGUgc2FtZSBsb2NhdGlvbi4gSWYgdGhleSBsaXZlIGluIHRoZSBzYW1lIGxvY2F0aW9uLCB0aGV5IGNhbiBkcml2ZSB0b2dldGhlci4gSG93ZXZlciwgZWFjaCBjYXIgY2FuIG9ubHkgZml0IHNvIG1hbnkgcGVvcGxlLiBZb3Ugd2lsbCBiZSBnaXZlbiwgZm9yIGVhY2ggcGVyc29uLCB3aGVyZSB0aGV5IGxpdmUsIGFuZCB3aGV0aGVyIHRoZXkgYXJlIGludG94aWNhdGVkLiBJbiBhZGRpdGlvbiwgeW91IHdpbGwgYmUgZ2l2ZW4gZm9yIGVhY2ggY2FyIHdoZXJlIGl0ICZsZHF1bztsaXZlcyZyZHF1bzssIGFuZCBob3cgbWFueSBwZW9wbGUgaXQgc2VhdHMuIEEgY2FyIGNhbiBiZSBkcml2ZW4gYnkgYW55b25lIGxpdmluZyBhdCBpdHMgbG9jYXRpb24sIHNvIGxvbmcgYXMgaGVcL3NoZSBpcyBzb2Jlci4gWW91IGFyZSB0byBkZXRlcm1pbmUgaG93IG1hbnkgcGVvcGxlIHdpbGwgbm90IGJlIGFibGUgdG8gZ2V0IGhvbWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhIG51bWJlciBLICZnZTsgMSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBpbnB1dCBkYXRhIHNldHMgaW4gdGhlIGZpbGUuIFRoaXMgaXMgZm9sbG93ZWQgYnkgSyBkYXRhIHNldHMgb2YgdGhlIGZvbGxvd2luZyBmb3JtOjxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgbGluZSBvZiBhIGRhdGEgc2V0IGNvbnRhaW5zIHRocmVlIG51bWJlcnMgbixjLFx1MjExMy4gbiAmbGU7IDUwMCBpcyB0aGUgbnVtYmVyIG9mIGZyaWVuZHMsIGMgJmxlOyBuIHRoZSBudW1iZXIgb2YgY2FycywgYW5kIFx1MjExMyAmbGU7IGMgdGhlIG51bWJlciBvZiBsb2NhdGlvbnMgd2hlcmUgcGVvcGxlIGxpdmUuPFwvcD5cclxuXHJcbjxwPk5leHQgYXJlIG4gbGluZXMsIGVhY2ggZGVzY3JpYmluZyBhIGZyaWVuZC4gRm9yIGVhY2ggZnJpZW5kLCB5b3Ugd2lsbCBiZSBnaXZlbiBhIG51bWJlciBiZXR3ZWVuIDEgYW5kIFx1MjExMywgdGhlIGxvY2F0aW9uIHdoZXJlIGhlXC9zaGUgbGl2ZXMsIGZvbGxvd2VkIGJ5IHRoZSBsZXR0ZXIgJmxzcXVvO0kmcnNxdW87IChmb3IgaW50b3hpY2F0ZWQpIG9yICZsc3F1bztTJnJzcXVvOyAoZm9yIHNvYmVyKS48XC9wPlxyXG5cclxuPHA+VGhpcyBpcyBmb2xsb3dlZCBieSBjIGxpbmVzLCBlYWNoIGRlc2NyaWJpbmcgYSBjYXIsIGJ5IGdpdmluZyBpdHMgbG9jYXRpb24gKGFuIGludGVnZXIgYmV0d2VlbiAxIGFuZCBcdTIxMTMpIGFuZCBpdHMgY2FwYWNpdHkgKGFuIGludGVnZXIgYmV0d2VlbiAyIGFuZCA4KS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCwgZmlyc3Qgb3V0cHV0ICZsZHF1bztEYXRhIFNldCB4OiZyZHF1bzsgb24gYSBsaW5lIGJ5IGl0c2VsZiwgd2hlcmUgeCBpcyBpdHMgbnVtYmVyLiBUaGVuLCBvdXRwdXQgdGhlIG51bWJlciBvZiBmcmllbmRzIHdobyB3aWxsIG5lZWQgdG8gc3RheSBhdCB5b3VyIGFwYXJ0bWVudCAoeW91IHRyeSB0byBoYXZlIGFzIGZldyBhcyBwb3NzaWJsZSBzdGF5KS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

University > The USC Programming Contest > Spring 2007 F번