Missile

Ramainya kasus terorisme saat ini, membuat Pak Dengklek mendapatkan ide berikut ini untuk salah satu soal Olimpiade Sains Nasional 2010.

Diberikan informasi lokasi N buah rumah yang terletak di sepanjang jalan yang diberi nomor antara 1 sampai dengan 100 000 (termasuk mungkin 1 atau 100 000 itu sendiri) yang menyatakan posisi rumah tersebut dan informasi jangkauan M buah misil yang dapat digunakan untuk menghancurkan salah satu rumah. Sebuah misil hanya dapat menghancurkan sebuah rumah yang diberikan informasi nomornya dan berada dalam jangkauan misil tersebut. Tugasnya cukup sederhana yakni untuk menghitung berapa banyak rumah maksimal yang dapat dihancurkan dengan menggunakan maksimal M buah misil tersebut.

Bantulah Pak Dengklek untuk menguji seberapa sulit ide soal tersebut dengan membuat contoh solusinya.

FORMAT MASUKAN

Baris pertama berisi dua buah bilangan bulat N (1 ≤ N ≤ 1 000) dan M (1 ≤ M ≤ 1 000). Baris kedua berisi N buah bilangan bulat dipisahkan spasi yang merupakan informasi nomor rumah-rumah. Tidak ada dua rumah yang bernomor sama.

M baris berikutnya masing-masing berisi dua buah bilangan bulat A dan B (1 ≤ A, B ≤ 100 000) yang menyatakan ujung kiri jangkauan dan ujung kanan jangkauan misil tersebut.

Pada lima puluh persen masukan, tidak akan terdapat dua buah misil dimana jangkauan misil pertama sepenuhnya ada di dalam jangkauan misil kedua. Dengan kata lain, tidak akan terdapat dua buah misil dimana ujung kiri jangkauan misil pertama berada lebih kanan dari ujung kiri jangkauan misil kedua sedangkan ujung kanan jangkauan misil pertama berada lebih kiri dari ujung kanan jangkauan misil kedua.

FORMAT KELUARAN

Sebuah bilangan bulat yang menyatakan banyak rumah maksimal yang dapat dihancurkan.

CONTOH MASUKAN 1

3 3
1 5 10
1 2
9 12
8 11

CONTOH KELUARAN 1

2

CONTOH MASUKAN 2

3 3
1 2 5
4 5
1 5
2 4

CONTOH KELUARAN 2

3

CONTOH MASUKAN 3

3 3
1 4 5
1 2
1 5
2 4

CONTOH KELUARAN 3

3

Penjelasan

Pada contoh pertama, misil pertama (dengan jangkauan 1 2) dapat dipakai untuk menghancurkan rumah bernomor 1, sedangkan rumah bernomor 5 tidak mungkin dihancurkan oleh misil kedua (dengan jangkauan 9 12) maupun ketiga (dengan jangkauan 8 11) karena nomornya tidak ada di dalam jangkauan kedua misil tersebut; namun salah satu dari misil kedua atau ketiga dapat digunakan untuk menghancurkan rumah bernomor 10.

Pada contoh kedua, misil pertama dapat dipakai untuk menghancurkan rumah bernomor 5, misil kedua untuk rumah bernomor 1, dan misil ketiga untuk rumah bernomor 2. Sedangkan pada contoh ketiga, misil pertama dapat dipakai untuk menghancurkan rumah bernomor 1, misil kedua untuk rumah bernomor 5, dan misil ketiga untuk rumah bernomor 2.