Shuriken Kết thúc - Một lần nữa


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Sau trận chiến cuối cùng với Kibaoni Gengetsu, cả 6 thành viên Ninninger đều trở thành Last Ninja theo con đường của họ. Nhưng sau 10 năm, một thế lực tương lai đã hồi sinh lại cho tên lãnh chúa Kibaoni Gengetsu.

Các thành viên Ninninger đã phải tập hợp lại. Sau một cuộc họp, mọi người đều chắc chắn rằng, lần này sẽ khó khăn hơn. Vì điều ước với Shuriken Kết thúc, nó đã tan biến mãi mãi, vì vậy, cả 6 không thể sử dụng được sức mạnh của nó.

Tuy nhiên, ông Tsumuji đã tìm ra cách tái tạo lại Shuriken Kết thúc. Hiện tại, trong nhà ông còn $N$ chiếc Shuriken Phong ấn, xếp từ 1 đến $N$ từ trái sang phải. Tương truyền, có một câu thần chú có thể giúp đánh thức sức mạnh và chuyển hóa các Shuriken này. Câu thần chú có đúng $N$ nhịp, nhịp thứ $i$ chuyển hóa $Shuriken$ thứ $p_i$ thành Nin Shuriken. Có tất cả $M$ đoạn Shuriken đặc biệt, đoạn thứ $i$ bắt đầu từ $l_i$ đến $r_i$ (các đoạn này có thể giao nhau).

Nhiệm vụ của đội là cần dừng câu chú đúng nhịp - là khi tồn tại một đoạn Shuriken đặc biệt có số Nin Shuriken lớn hơn số lượng Shuriken phong ấn.

Hãy giúp chiến đội tìm nhịp dừng đúng sớm nhất để có thể tạo ra Shuriken Kết thúc (đánh bại tên Kibaoni) một lần nữa.

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên $N, M \ (1 \le M \le N \le 10^5)$;
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i, r_i \ (1\le l_i \le r_i \le N)$;
  • Dòng cuối cùng chứa $N$ số nguyên $p_i \ (1\le p_i \le N)$ - dãy $p_i$ là một hoán vị của $N$ số tự nhiên đầu tiên.

Kết quả

  • Kết quả bài toán.

Ví dụ

Ví dụ 1

input

5 5
1 2
4 5
1 5
1 3
2 4
5 3 1 2 4

output

3

Comments

There are no comments at the moment.