시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB77633527744.968%

문제

학교 대표팀은 1부터 번호가 매겨진 저지를 학생 선수들에게 배분하고자 한다. 저지의 사이즈는 S, M, L 중 하나이다 (물론 S=small, M=medium, L=Large다).

각각의 선수들은 구체적인 저지의 번호와 선호하는 사이즈를 요구했다. 선수들은 만약 자신이 원했던 번호가 아니거나, 선호하는 사이즈보다 작은 사이즈의 옷을 받으면 불만이 생길 것이다. 그들을 만족시키기 위해서는, 요구하는 번호가 맞고 사이즈는 같거나 그 이상이어야 한다. 두 명의 학생들이 같은 저지를 받을 수은 없다.

조건을 만족하는 최대 학생 수를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄은 저지의 수인 J가 주어진다.

두 번째 줄은 선수들의 수인 A가 주어진다.

다음  J줄에는 등번호 j인 저지의 사이즈가 주어진다. (1 ≤ j ≤ J)

마지막 A줄에는 선수들이 요구하는 사이즈와 번호가 입력된다.

테스트케이스의 50%는 1 ≤ J ≤ 103 , 1 ≤ A ≤ 103 를 만족하고, 

나머지 50%는 1 ≤ J ≤ 106 , 1 ≤ A ≤ 106 를 만족한다.

출력

만족할 수 있는 최대의 선수의 수를 출력한다.

예제 입력 1

4
3
M
S
S
L
L 3
S 3
L 1

예제 출력 1

1

힌트

첫 번째 저지는 M이고, 3번째 선수가 L을 요구했기 때문에 첫 번째 저지는 주어질 수 없다. 두 번째 저지와 네 번째 저지는 요구된 적이 없고, 세 번째 저지는 S를 요구한 2번째 선수에게 주어진다.

W3sicHJvYmxlbV9pZCI6IjEwNzc0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjODAwXHVjOWMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NTlcdWFkNTAgXHViMzAwXHVkNDVjXHVkMzAwXHVjNzQwIDFcdWJkODBcdWQxMzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzljNCBcdWM4MDBcdWM5YzBcdWI5N2MgXHVkNTU5XHVjMGRkIFx1YzEyMFx1YzIxOFx1YjRlNFx1YzVkMFx1YWM4YyBcdWJjMzBcdWJkODRcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTVjXHViMmU0LiBcdWM4MDBcdWM5YzBcdWM3NTggXHVjMGFjXHVjNzc0XHVjOTg4XHViMjk0IFMsIE0sIEwgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNCAoXHViYjNjXHViODYwIFM9c21hbGwsIE09bWVkaXVtLCBMPUxhcmdlXHViMmU0KS48XC9wPlxyXG5cclxuPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1YzEyMFx1YzIxOFx1YjRlNFx1Yzc0MCBcdWFkNmNcdWNjYjRcdWM4MDFcdWM3NzggXHVjODAwXHVjOWMwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWMxMjBcdWQ2MzhcdWQ1NThcdWIyOTQgXHVjMGFjXHVjNzc0XHVjOTg4XHViOTdjIFx1YzY5NFx1YWQ2Y1x1ZDU4OFx1YjJlNC4gXHVjMTIwXHVjMjE4XHViNGU0XHVjNzQwIFx1YjljY1x1YzU3ZCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjNmQwXHVkNTg4XHViMzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM1NDRcdWIyYzhcdWFjNzBcdWIwOTgsIFx1YzEyMFx1ZDYzOFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWM3NzRcdWM5ODhcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YzBhY1x1Yzc3NFx1Yzk4OFx1Yzc1OCBcdWM2MzdcdWM3NDQgXHViYzFiXHVjNzNjXHViYTc0IFx1YmQ4OFx1YjljY1x1Yzc3NCBcdWMwZGRcdWFlMzggXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFkZjhcdWI0ZTRcdWM3NDQgXHViOWNjXHVjODcxXHVjMmRjXHVkMGE0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCwgXHVjNjk0XHVhZDZjXHVkNTU4XHViMjk0IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZGVcdWFjZTAgXHVjMGFjXHVjNzc0XHVjOTg4XHViMjk0IFx1YWMxOVx1YWM3MFx1YjA5OCBcdWFkZjggXHVjNzc0XHVjMGMxXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YzgwMFx1YzljMFx1Yjk3YyBcdWJjMWJcdWM3NDQgXHVjMjE4XHVjNzQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTU5XHVjMGRkIFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNzQwIFx1YzgwMFx1YzljMFx1Yzc1OCBcdWMyMThcdWM3NzggSlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNzQwIFx1YzEyMFx1YzIxOFx1YjRlNFx1Yzc1OCBcdWMyMThcdWM3NzggQVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAmbmJzcDtKXHVjOTA0XHVjNWQwXHViMjk0IFx1YjRmMVx1YmM4OFx1ZDYzOCBqXHVjNzc4Jm5ic3A7XHVjODAwXHVjOWMwXHVjNzU4IFx1YzBhY1x1Yzc3NFx1Yzk4OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDEgJmxlOyBqICZsZTsgSik8XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5IEFcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTIwXHVjMjE4XHViNGU0XHVjNzc0IFx1YzY5NFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWMwYWNcdWM3NzRcdWM5ODhcdWM2NDAgXHViYzg4XHVkNjM4XHVhYzAwIFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IDUwJVx1YjI5NCZuYnNwOzEgJmxlOyBKICZsZTsgMTA8c3VwPjM8XC9zdXA+Jm5ic3A7LCAxICZsZTsgQSAmbGU7IDEwPHN1cD4zPFwvc3VwPiBcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHVhY2UwLCZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWIwOThcdWJhMzhcdWM5YzAgNTAlXHViMjk0Jm5ic3A7MSAmbGU7IEogJmxlOyAxMDxzdXA+NjxcL3N1cD4mbmJzcDssIDEgJmxlOyBBICZsZTsgMTA8c3VwPjY8XC9zdXA+IFx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViOWNjXHVjODcxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwXHVjNzU4IFx1YzEyMFx1YzIxOFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzgwMFx1YzljMFx1YjI5NCBNXHVjNzc0XHVhY2UwLCAzXHViYzg4XHVjOWY4IFx1YzEyMFx1YzIxOFx1YWMwMCBMXHVjNzQ0IFx1YzY5NFx1YWQ2Y1x1ZDU4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM4MDBcdWM5YzBcdWIyOTQgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjODAwXHVjOWMwXHVjNjQwIFx1YjEyNCBcdWJjODhcdWM5ZjggXHVjODAwXHVjOWMwXHViMjk0IFx1YzY5NFx1YWQ2Y1x1YjQxYyBcdWM4MDFcdWM3NzQgXHVjNWM2XHVhY2UwLCBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzgwMFx1YzljMFx1YjI5NCBTXHViOTdjIFx1YzY5NFx1YWQ2Y1x1ZDU1YyAyXHViYzg4XHVjOWY4IFx1YzEyMFx1YzIxOFx1YzVkMFx1YWM4YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDc3NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkplcnNleXMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgc2Nob29sIHRlYW0gaXMgdHJ5aW5nIHRvIGFzc2lnbiBqZXJzZXlzIG51bWJlcmVkIDEsIDIsIDMsIC4gLiAuICwgSiB0byBzdHVkZW50IGF0aGxldGVzLiBUaGUgc2l6ZSBvZiBlYWNoIGplcnNleSBpcyBlaXRoZXIgc21hbGwgKFMpLCBtZWRpdW0gKE0pIG9yIGxhcmdlIChMKS48XC9wPlxyXG5cclxuPHA+RWFjaCBhdGhsZXRlIGhhcyByZXF1ZXN0ZWQgYSBzcGVjaWZpYyBqZXJzZXkgbnVtYmVyIGFuZCBhIHByZWZlcnJlZCBzaXplLiBUaGUgYXRobGV0ZXMgd2lsbCBub3QgYmUgc2F0aXNmaWVkIHdpdGggYSBqZXJzZXkgdGhhdCBpcyB0aGUgd3JvbmcgbnVtYmVyIG9yIHRoYXQgaXMgc21hbGxlciB0aGFuIHRoZWlyIHByZWZlcnJlZCBzaXplLiBUaGV5IHdpbGwgYmUgc2F0aXNmaWVkIHdpdGggYSBqZXJzZXkgdGhhdCBpcyB0aGVpciBwcmVmZXJyZWQgc2l6ZSBvciBsYXJnZXIgYXMgbG9uZyBhcyBpdCBpcyB0aGUgcmlnaHQgbnVtYmVyLiBUd28gc3R1ZGVudHMgY2Fubm90IGJlIGdpdmVuIHRoZSBzYW1lIGplcnNleS48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIGRldGVybWluZSB0aGUgbWF4aW11bSBudW1iZXIgb2YgcmVxdWVzdHMgdGhhdCBjYW4gYmUgc2F0aXNmaWVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgaXMgdGhlIGludGVnZXIgSiB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGplcnNleXMuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBpcyB0aGUgaW50ZWdlciBBIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgYXRobGV0ZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IEogbGluZXMgYXJlIGVhY2ggdGhlIGNoYXJhY3RlciBTLCBNIG9yIEwuIExpbmUgaiBnaXZlcyB0aGUgc2l6ZSBvZiBqZXJzZXkgaiAoMSAmbGU7IGogJmxlOyBKKS48XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgQSBsaW5lcyBhcmUgZWFjaCB0aGUgY2hhcmFjdGVyIFMsIE0gb3IgTCBmb2xsb3dlZCBieSBhIHNwYWNlIGZvbGxvd2VkIGJ5IGFuIGludGVnZXIuIExpbmUgYSAoMSAmbGU7IGEgJmxlOyBBKSBnaXZlcyB0aGUgcmVxdWVzdGVkIHNpemUgYW5kIGplcnNleSBudW1iZXIgZm9yIGF0aGxldGUgYSB3aGVyZSB0aGUgYXRobGV0ZXMgYXJlIG51bWJlcmVkIDEsIDIsIDMsIC4gLiAuICwgQS48XC9wPlxyXG5cclxuPHA+Rm9yIDUwJSBvZiB0aGUgdGVzdCBjYXNlcywgMSAmbGU7IEogJmxlOyAxMDxzdXA+MzxcL3N1cD4gYW5kIDEgJmxlOyBBICZsZTsgMTA8c3VwPjM8XC9zdXA+LjxcL3A+XHJcblxyXG48cD5Gb3IgdGhlIHJlbWFpbmluZyA1MCUgb2YgdGhlIHRlc3QgY2FzZXMsIDEgJmxlOyBKICZsZTsgMTA8c3VwPjY8XC9zdXA+IGFuZCAxICZsZTsgQSAmbGU7IDEwPHN1cD42PFwvc3VwPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHdpbGwgY29uc2lzdCBvZiBhIHNpbmdsZSBpbnRlZ2VyIHdoaWNoIGlzIHRoZSBtYXhpbXVtIG51bWJlciBvZiByZXF1ZXN0cyB0aGF0IGNhbiBiZSBzYXRpc2ZpZWQuPFwvcD5cclxuIiwiaGludCI6IjxwPkplcnNleSAxIGNhbm5vdCBiZSBhc3NpZ25lZCBiZWNhdXNlIGl0IGlzIG1lZGl1bSBhbmQgYXRobGV0ZSAzIHJlcXVlc3RlZCBsYXJnZS4gTm8gYXRobGV0ZSByZXF1ZXN0ZWQgamVyc2V5IDIgb3IgNC4gSmVyc2V5IDMgKHNtYWxsKSBjYW4gYmUgYXNzaWduZWQgYXRobGV0ZSAyIChzbWFsbCkgYnV0IG5vdCBhdGhsZXRlIDEgKGxhcmdlKS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > Canadian Computing Competition & Olympiad > 2015 > CCC 2015 Senior Division 2번

  • 문제를 번역한 사람: jjwdi0