题目描述

小婷有 $C$ 个可用时刻，每个时刻最多完成一次会面；另有 $N$ 个会面请求，第 $j$ 个允许在闭区间 $[A_j,B_j]$ 内任一时刻进行。每个请求至多安排一次。求最多能安排多少次会面。

输入格式

第一行 $C,N$。接下来 $C$ 行为可用时刻 $T_i$，再接下来 $N$ 行为 $A_j,B_j$。

输出格式

输出最大匹配数。

输入

110 1
387334144
772411556
410216656
503353338
644441517
678893941
980116394
425907341
840721433
330108448
392991835
804773412
219731170
824742891
810772577
506134561
369551681
27290652
800391782
175644251
584713410
605135057
340670431
354010469
795632807
333653033
617588059
248744362
803544192
866294363
52002898
464368979
331908784
237503331
254235435
687669163
746050101
880635906
532842322
377643629
701767327
35473213
906298076
691779263
919038671
281274509
838077594
866208468
964379587
242493721
828480554
908771085
485505946
799514357
582656414
963525899
549198852
611889574
180667035
776388040
915944426
114170482
257480064
276441379
694141119
551655337
217136545
862729984
875734850
35450964
142500465
531756974
413678130
506379565
931988506
821139831
573420803
268132160
93227752
511854642
500640394
230784927
314695197
538623918
974332058
897670230
487590990
737354549
928446256
524021622
583571639
68335588
271382636
70288026
59350939
62343624
482115458
455649191
928164878
330030092
855939679
309066420
900220279
31853668
249187628
887356039
994599853
923607404
713279533
335208345
239062235 567621597

输出

1

输入

64 44
627195984
405976412
749756399
342839305
25599190
163614675
975374177
525626951
136970650
695528304
63688431
980827288
840471827
266277335
49755304
894641669
833060907
864661573
632541821
758351647
818718101
780732739
734867687
316682496
429293693
491797274
436020818
46984534
517698372
928945914
650475430
287400801
950048136
246706031
240747697
925952025
922899724
230050168
792180897
712952789
175449303
735532179
281987637
599570387
864003130
467023884
760804003
165411553
915169442
990819845
938874630
66136510
127737735
626520171
459860628
118674112
282447609
838245030
953493146
894530870
94780969
569911494
117558018
342499399
651775242 742568841
186093521 803972247
425581150 986570352
529898242 811098534
254089175 720034377
635652781 796494260
603751927 856704309
228518941 240088668
832662223 887210450
502515875 673846728
236484192 802789224
816990734 971262169
314137059 467675113
201965291 219845480
600024229 845245841
276493673 329874058
759637495 971895386
702499230 790179482
870975036 992816434
419548993 660641144
58162056 979121548
938988072 967543329
463583080 493293901
572016430 620482969
645530869 802715483
606403301 606457331
823973940 887178862
810591795 949961208
957941672 998338107
997941900 998499058
216355599 849635007
685150808 890874616
351081706 672296686
742502127 946868725
395506961 500919763
143666431 950003296
753578146 794360149
895766936 946757637
533559407 787667922
431730696 663994677
918740456 938351226
994559723 998607920
576695730 952939366
245311598 835881374

输出

40

输入

41 61
418452705
319875071
605181364
166203217
590601878
989156278
156061490
320340425
461389562
850763241
411387051
7732768
828932153
125248984
357516665
784907444
789085466
470563997
859227631
711527944
324938361
191329738
155947936
774772889
899212136
725106138
45776591
330319745
67278977
909222655
42658769
188180047
816513948
580218582
73066797
213482846
2171312
555465667
785064920
49722760
470277023
729084251 839245159
533632225 613150932
613941518 781794140
267614105 722941102
518513837 733968260
73111780 899874461
746820895 859193007
319994283 634120083
933919330 962052952
368510448 736779306
136047 12292910
537401615 553379908
616784283 677382487
184651124 383434612
338478512 903077926
145896018 344531482
31180744 735110926
270581364 846199213
319073277 505515181
443811086 994337920
118030199 403832522
355185641 775990844
771787655 789412868
616738494 864991657
347820075 712721823
578506966 683066795
288507769 979545140
906988745 917348218
678956502 775800234
455219534 800199497
537382547 668368013
553173692 612341207
10305822 976516166
836064770 904015608
222165570 763814994
146448583 850201176
598370468 672747084
34111499 214272596
836341399 851656183
49984034 600878555
338106192 630087170
824684625 889803809
539917598 550243283
998889012 999228668
844743546 959339639
265060492 402538259
859188376 975586603
85773754 385948753
429825940 487883447
728075734 869205718
724753726 756925209
327547789 548038290
880142106 989767174
67422881 296281027
948334318 978844349
438017234 695031963
56887007 892480423
689402931 903276084
236051585 345503745
31326727 373282149
169589847 315235599

输出

40

数据范围

$1\le C,N\le20000$；$A_j,B_j,T_i$ 均为不超过 $10^9$ 的非负整数。