시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 391 99 80 28.674%

문제

농부 존의 소들은 효율적으로 길을 건너는 방법을 터득하고 있다. 그들은 길 건너기의 달인인 닭의 도움을 받기로 했다.

안타깝게도 닭은 매우 바쁜 동물이라, 소를 도와줄 시간이 별로 없다. 농장에 C마리(1 ≤ C ≤ 20,000)의 닭이 있고, 1번부터 C번까지 번호가 붙어 있다. i번 닭은 정확히 Ti초에만 소를 도와줄 수 있다. 하지만 닭은 길 건너기의 달인이므로 소를 데리고도 순식간에 길을 건널 수 있다. 소는 할 일이 없어서 여유롭게 길을 건널 수 있다. 소는 총 N마리(1 ≤ N ≤ 20,000)가 있고, 마찬가지로 1번부터 N번까지 번호가 붙어 있다. j번 소는 Aj초부터 Bj초까지 길을 건널 수 있다. j번 소가 i번 닭의 도움을 받아 길을 건너려면  Aj ≤ Ti ≤ Bj를 만족해야 한다.

소는 최대 한 마리의 닭에게만 도움을 받을 수 있고, 닭 역시 최대 한 마리의 소만 도와줄 수 있다. 도움을 받을 수 있는 소가 최대 몇 마리인지 구해보자.

입력

첫 줄에 C와 N이 주어진다. 다음 C줄에는 T1…TC가 주어지고, 그 다음 N줄에는 Aj와 Bj(A≤ Bj)가 주어진다. A, B, T는 모두 최대 1,000,000,000인 음이 아닌 정수이고, 같을 수도 있다.

출력

도움을 받을 수 있는 소가 최대 몇 마리인지 출력한다.

예제 입력 1

5 4
7
8
6
2
9
2 5
4 9
0 3
8 13

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjE0NDY0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwIDQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjE4ZFx1YmQ4MCBcdWM4NzRcdWM3NTggXHVjMThjXHViNGU0XHVjNzQwIFx1ZDZhOFx1YzcyOFx1YzgwMVx1YzczY1x1Yjg1YyBcdWFlMzhcdWM3NDQgXHVhYzc0XHViMTA4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWQxMzBcdWI0ZGRcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI0ZTRcdWM3NDAgXHVhZTM4IFx1YWM3NFx1YjEwOFx1YWUzMFx1Yzc1OCBcdWIyZWNcdWM3NzhcdWM3NzggXHViMmVkXHVjNzU4IFx1YjNjNFx1YzZjMFx1Yzc0NCBcdWJjMWJcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDhcdWQwYzBcdWFlNWRcdWFjOGNcdWIzYzQgXHViMmVkXHVjNzQwIFx1YjllNFx1YzZiMCBcdWJjMTRcdWMwNWMgXHViM2Q5XHViYjNjXHVjNzc0XHViNzdjLCBcdWMxOGNcdWI5N2MgXHViM2M0XHVjNjQwXHVjOTA0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWJjYzRcdWI4NWMgXHVjNWM2XHViMmU0LiBcdWIxOGRcdWM3YTVcdWM1ZDAgQ1x1YjljOFx1YjlhYygxICZsZTsgQyAmbGU7IDIwLDAwMClcdWM3NTggXHViMmVkXHVjNzc0IFx1Yzc4OFx1YWNlMCwgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBDXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjQgXHVjNzg4XHViMmU0LiBpXHViYzg4IFx1YjJlZFx1Yzc0MCBcdWM4MTVcdWQ2NTVcdWQ3ODggVDxzdWI+aTxcL3N1Yj5cdWNkMDhcdWM1ZDBcdWI5Y2MgXHVjMThjXHViOTdjIFx1YjNjNFx1YzY0MFx1YzkwNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHViMmVkXHVjNzQwIFx1YWUzOCBcdWFjNzRcdWIxMDhcdWFlMzBcdWM3NTggXHViMmVjXHVjNzc4XHVjNzc0XHViYmMwXHViODVjIFx1YzE4Y1x1Yjk3YyBcdWIzNzBcdWI5YWNcdWFjZTBcdWIzYzQgXHVjMjFjXHVjMmRkXHVhYzA0XHVjNWQwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMTAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjMThjXHViMjk0IFx1ZDU2MCBcdWM3N2NcdWM3NzQgXHVjNWM2XHVjNWI0XHVjMTFjIFx1YzVlY1x1YzcyMFx1Yjg2ZFx1YWM4YyBcdWFlMzhcdWM3NDQgXHVhYzc0XHViMTEwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzE4Y1x1YjI5NCBcdWNkMWQgTlx1YjljOFx1YjlhYygxICZsZTsgTiAmbGU7IDIwLDAwMClcdWFjMDAgXHVjNzg4XHVhY2UwLCBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzBcdWI4NWMgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjQgXHVjNzg4XHViMmU0LiBqXHViYzg4IFx1YzE4Y1x1YjI5NCBBPHN1Yj5qPFwvc3ViPlx1Y2QwOFx1YmQ4MFx1ZDEzMCBCPHN1Yj5qPFwvc3ViPlx1Y2QwOFx1YWU0Y1x1YzljMCBcdWFlMzhcdWM3NDQgXHVhYzc0XHViMTEwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIGpcdWJjODggXHVjMThjXHVhYzAwIGlcdWJjODggXHViMmVkXHVjNzU4IFx1YjNjNFx1YzZjMFx1Yzc0NCBcdWJjMWJcdWM1NDQgXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwOFx1YjgyNFx1YmE3NCAmbmJzcDtBPHN1Yj5qIDxcL3N1Yj4mbGU7IFQ8c3ViPmk8XC9zdWI+ICZsZTsgQjxzdWI+ajxcL3N1Yj5cdWI5N2MgXHViOWNjXHVjODcxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMThjXHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWQ1NWMgXHViOWM4XHViOWFjXHVjNzU4IFx1YjJlZFx1YzVkMFx1YWM4Y1x1YjljYyBcdWIzYzRcdWM2YzBcdWM3NDQgXHViYzFiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YjJlZCBcdWM1ZWRcdWMyZGMgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWI5YzhcdWI5YWNcdWM3NTggXHVjMThjXHViOWNjIFx1YjNjNFx1YzY0MFx1YzkwNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIzYzRcdWM2YzBcdWM3NDQgXHViYzFiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMThjXHVhYzAwIFx1Y2Q1Y1x1YjMwMCBcdWJhODcgXHViOWM4XHViOWFjXHVjNzc4XHVjOWMwIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgQ1x1YzY0MCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIENcdWM5MDRcdWM1ZDBcdWIyOTQgVDxzdWI+MTxcL3N1Yj4maGVsbGlwO1Q8c3ViPkM8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHVhZGY4IFx1YjJlNFx1Yzc0YyBOXHVjOTA0XHVjNWQwXHViMjk0IEE8c3ViPmo8XC9zdWI+XHVjNjQwIEI8c3ViPmo8XC9zdWI+KEE8c3ViPmombmJzcDs8XC9zdWI+JmxlOyBCPHN1Yj5qPFwvc3ViPilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBBLCBCLCBUXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWNkNWNcdWIzMDAgMSwwMDAsMDAwLDAwMFx1Yzc3OCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YWNlMCwgXHVhYzE5XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViM2M0XHVjNmMwXHVjNzQ0IFx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzE4Y1x1YWMwMCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YjljOFx1YjlhY1x1Yzc3OFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTQ0NjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXaHkgRGlkIHRoZSBDb3cgQ3Jvc3MgdGhlIFJvYWQgKFNpbHZlcikiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huJiMzOTtzIGNvd3MgYXJlIHRyeWluZyB0byBsZWFybiB0byBjcm9zcyB0aGUgcm9hZCBlZmZlY3RpdmVseS4gUmVtZW1iZXJpbmcgdGhlIG9sZCAmcXVvdDt3aHkgZGlkIHRoZSBjaGlja2VuIGNyb3NzIHRoZSByb2FkPyZxdW90OyBqb2tlLCB0aGV5IGZpZ3VyZSB0aGUgY2hpY2tlbnMgbXVzdCBiZSBleHBlcnRzIG9uIGNyb3NzaW5nIHRoZSByb2FkLCBhbmQgZ28gb2ZmIGluIHNlYXJjaCBvZiBjaGlja2VucyB0byBoZWxwIHRoZW0uPFwvcD5cclxuXHJcbjxwPkFzIGl0IHR1cm5zIG91dCwgY2hpY2tlbnMgYXJlIHZlcnkgYnVzeSBjcmVhdHVyZXMgYW5kIGhhdmUgbGltaXRlZCB0aW1lIHRvIGhlbHAgdGhlIGNvd3MuIFRoZXJlIGFyZSZuYnNwO0MmbmJzcDtjaGlja2VucyBvbiB0aGUgZmFybSAoMSAmbGU7IEMgJmxlOyAyMCwwMDApLCBjb252ZW5pZW50bHkgbnVtYmVyZWQmbmJzcDsxJmhlbGxpcDtDLCBhbmQgZWFjaCBjaGlja2VuJm5ic3A7aSZuYnNwO2lzIG9ubHkgd2lsbGluZyB0byBoZWxwIGEgY293IGF0IHByZWNpc2VseSB0aW1lJm5ic3A7VDxzdWI+aTxcL3N1Yj4uIFRoZSBjb3dzLCBuZXZlciBpbiBhIGh1cnJ5LCBoYXZlIG1vcmUgZmxleGliaWxpdHkgaW4gdGhlaXIgc2NoZWR1bGVzLiBUaGVyZSBhcmUmbmJzcDtOJm5ic3A7Y293cyBvbiB0aGUgZmFybSAoMSAmbGU7IE4gJmxlOyAyMCwwMDApLCBjb252ZW5pZW50bHkgbnVtYmVyZWQmbmJzcDsxJmhlbGxpcDtOLCB3aGVyZSBjb3cmbmJzcDtqJm5ic3A7aXMgYWJsZSB0byBjcm9zcyB0aGUgcm9hZCBiZXR3ZWVuIHRpbWUmbmJzcDtBPHN1Yj5qPFwvc3ViPiBhbmQgdGltZSZuYnNwO0I8c3ViPmo8XC9zdWI+LiBGaWd1cmluZyB0aGUgJnF1b3Q7YnVkZHkgc3lzdGVtJnF1b3Q7IGlzIHRoZSBiZXN0IHdheSB0byBwcm9jZWVkLCBlYWNoIGNvdyZuYnNwO2ombmJzcDt3b3VsZCBpZGVhbGx5IGxpa2UgdG8gZmluZCBhIGNoaWNrZW4mbmJzcDtpJm5ic3A7dG8gaGVscCBoZXIgY3Jvc3MgdGhlIHJvYWQ7IGluIG9yZGVyIGZvciB0aGVpciBzY2hlZHVsZXMgdG8gYmUgY29tcGF0aWJsZSwmbmJzcDtpJm5ic3A7YW5kIGombmJzcDttdXN0IHNhdGlzZnkmbmJzcDtBPHN1Yj5qIDxcL3N1Yj4mbGU7IFQ8c3ViPmk8XC9zdWI+ICZsZTsgQjxzdWI+ajxcL3N1Yj4uPFwvcD5cclxuXHJcbjxwPklmIGVhY2ggY293IGNhbiBiZSBwYWlyZWQgd2l0aCBhdCBtb3N0IG9uZSBjaGlja2VuIGFuZCBlYWNoIGNoaWNrZW4gd2l0aCBhdCBtb3N0IG9uZSBjb3csIHBsZWFzZSBoZWxwIGNvbXB1dGUgdGhlIG1heGltdW0gbnVtYmVyIG9mIGNvdy1jaGlja2VuIHBhaXJzIHRoYXQgY2FuIGJlIGNvbnN0cnVjdGVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgQyZuYnNwO2FuZCZuYnNwO04uIFRoZSBuZXh0Jm5ic3A7QyZuYnNwO2xpbmVzIGNvbnRhaW4mbmJzcDtUPHN1Yj4xPFwvc3ViPiZoZWxsaXA7VDxzdWI+QzxcL3N1Yj4sIGFuZCB0aGUgbmV4dCZuYnNwO04mbmJzcDtsaW5lcyBjb250YWluJm5ic3A7QTxzdWI+ajxcL3N1Yj4gYW5kJm5ic3A7QjxzdWI+ajxcL3N1Yj4mbmJzcDsoQTxzdWI+aiZuYnNwOzxcL3N1Yj4mbGU7IEI8c3ViPmo8XC9zdWI+KSBmb3ImbmJzcDtqPTEmaGVsbGlwO04uIFRoZSZuYnNwO0EmIzM5O3MsJm5ic3A7QiYjMzk7cywgYW5kJm5ic3A7VCYjMzk7cyBhcmUgYWxsIG5vbi1uZWdhdGl2ZSBpbnRlZ2VycyAobm90IG5lY2Vzc2FyaWx5IGRpc3RpbmN0KSBvZiBzaXplIGF0IG1vc3QgMSwwMDAsMDAwLDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QbGVhc2UgY29tcHV0ZSB0aGUgbWF4aW11bSBwb3NzaWJsZSBudW1iZXIgb2YgY293LWNoaWNrZW4gcGFpcnMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==