Đoạn nhiều số 1

Cho một dãy \(a\) gồm \(n\) phần tử, ban đầu tất cả đều bằng \(0\), và \(m\) đoạn con \([L_i, R_i]\) (đoạn gồm các phần tử \(a_{L_i}, a_{L_i+1}, \dots, a_{R_i}\)).

Một đoạn được gọi là tốt nếu trong đoạn đó số phần tử bằng \(1\) nhiều hơn hẳn số phần tử bằng \(0\). Ví dụ với \(a = [1, 0, 1, 0, 1]\), đoạn \([1, 5]\) là tốt (có \(3\) số \(1\) và \(2\) số \(0\)), còn đoạn \([3, 4]\) và đoạn \([4, 4]\) thì không.

Sau đó có \(q\) thao tác, thực hiện lần lượt theo thứ tự đã cho; thao tác thứ \(j\) cho một số \(x_j\) và gán \(a_{x_j} = 1\) (nếu đã bằng \(1\) rồi thì không thay đổi gì).

Hãy tìm số thao tác ít nhất cần thực hiện (theo đúng thứ tự, tức là xét tiền tố của dãy thao tác) sao cho có ít nhất một trong \(m\) đoạn là đoạn tốt. Nếu sau khi thực hiện cả \(q\) thao tác mà vẫn không có đoạn nào tốt, in ra \(-1\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L_i\), \(R_i\).
• Dòng tiếp theo chứa số nguyên \(q\).
• \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(x_j\).

Output

In ra một số nguyên là số thao tác ít nhất, hoặc \(-1\) nếu không thể.

Constraints

• \(1 \le n, m, q \le 10^5\)
• \(1 \le L_i \le R_i \le n\)
• \(1 \le x_j \le n\)

Sample Input 1

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

Sample Output 1

3

Sample Input 2

5 2
1 5
2 4
3
1
1
5

Sample Output 2

-1

Explanation

• Ví dụ 1: sau \(2\) thao tác (\(a_3 = a_5 = 1\)) đoạn \([3, 6]\) có \(2\) số \(1\) và \(2\) số \(0\) (chưa tốt), đoạn \([2, 3]\) có \(1\) số \(1\) và \(1\) số \(0\) (chưa tốt). Sau thao tác thứ \(3\) (\(a_4 = 1\)), đoạn \([3, 6]\) có \(3\) số \(1\) và \(1\) số \(0\) nên tốt.
• Ví dụ 2: sau cả \(3\) thao tác chỉ có \(a_1 = a_5 = 1\); đoạn \([1, 5]\) có \(2\) số \(1\) và \(3\) số \(0\), đoạn \([2, 4]\) có \(0\) số \(1\), nên không đoạn nào tốt.