Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_28_04 - Zawody sportowe

W szkole Jasia trwają zawody sportowe. Zawody te składają się z N dyscyplin. W każdej dyscyplinie można zdobyć pewną liczbę punktów i na podstawie sumy zdobytych punktów tworzony jest ranking ogólny. Jaś właśnie ukończył ultramaraton, ostatnią dyscyplinę. Jako, że wysiłek, który musiał włożyć w bieg był olbrzymi, Jaś zapomniał ile dokładnie punktów zdobył. Pamięta tylko, że z i'tej dyscypliny zdobył conajmniej ai punktów, lecz nie więcej niż bi punktów. Ranking ogólny ma zostać upubliczniony dopiero jutro, a Jaś chciałby już się dowiedzieć jakie miejsca moża zająć dlatego postanowił zapytać swoich rywali o to, ile punktów w sumie zdobyli. Rywali jest M oraz każdy z nich ma zapisaną dokładną ilość punktów zdobytych za wszystkie dyscypliny. Jaś dostarczył Ci powyższe dane i zadał Ci pytanie: ile różnych miejsc może zająć w rankingu ogólnym ?

Jeśli kilka osób ma taką samą liczbę punktów to zajmują one to samo miejsce. Np. jeśli wszyscy rywale i Jaś mają taką samą liczbę punktów to wszyscy zajmują miejsce pierwsze.

Wejście

W pierwszej linii wejścia znajduję się liczba zestawów danych T (1 ≤ T ≤ 103). Następnie każdy zestaw danych opisany jest w następujący sposób.

W pierwszej linii zestawu danych dane są dwie liczby N i M (1 ≤ N, M ≤ 103).

W następnych N liniach dane są liczby ai oraz bi (1 ≤ ai < bi ≤ 104).

W ostatniej linii zestawu danych dane jest M dodatnich liczb całkowitych nie większych niż 109. i-ta liczba informuje o sumarycznej ilości punktów zdobytych przez i-tego rywala Jasia.

Wyjście

Dla każdego zestawu danych należy wypisać jedną liczbę, ilość różnych miejsc jakie może zająć Jaś w rankingu ogólnym.

Przykład

Wejście:
3
5 8
3 6
2 3
3 4
7 9
10 16
5 1 19 33 87 1 25 38
1 1
1 10
5
9 60
1 2
2 3
3 4
4 5
1 6
9 10
4 7
7 9
8 11
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

Wyjście:
3
2
19



Dodane przez:Bartek
Data dodania:2016-06-16
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.