Problem description

Janek gra ze swoim przyjacielem Karolem w grę. Na stole znajduje się n kubków, ponumerowanych kolejnymi liczbami naturalnymi od 1 do n, z których każdy ma przypisaną wartość. Oprócz kubków dostępny jest multizbiór przedziałów, a każdy z graczy ma nieograniczoną liczbę kulek. Gra przebiega w systemie turowym, w którym gracze wykonują ruchy naprzemiennie, a zaczynającym jest Janek.

• W każdej turze gracz wybiera jeden przedział (oznaczmy jako [l,r]) z multizbioru i wrzuca po jednej kulce do każdego kubka o numerze z przedziału [l,r].
• Po wrzuceniu kulek do kubków wybrany przedział zostaje usunięty z dostępnego multizbioru.
• Janek zawsze zaczyna grę.
• Po zakończeniu gry wynikiem Janka jest maksymalna wartość kubka, w których ma więcej kulek niż Karol lub  − 1, jeśli nie ma żadnego takiego kubka.
• Janek stara się maksymalizować swoją wartość, podczas gdy Karol dąży do jej zminimalizowania.
• Gra kończy się w momencie, kiedy żaden z graczy nie może wykonać ruchu, ponieważ wszystkie przedziały zostały wykorzystane.

Twoim zadaniem jest określenie, jaki maksymalny wynik może osiągnąć Janek, biorąc pod uwagę optymalną strategię obu graczy.

Wejście

Pierwszy wiersz wejścia zawiera liczbę t - przypadków testowych. Następnie dla każdego przypadku testowego:

• Liczba całkowita n — liczba kubków.
• n liczb całkowitych a₁, a₂, …, a_n — wartości kubków.
• Liczba całkowita m — liczba dostępnych przedziałów.
• m par liczb całkowitych l_i, r_i — przedziały, do których można wrzucać kulki.

Wyjście

Dla każdego przypadku testowego program powinien wypisać maksymalny wynik, który może uzyskać Janek, uwzględniając optymalną strategię obu graczy.

Ograniczenia

• t ≤ 10 000 — liczba przypadków testowych.
• 1 ≤ n ≤ 100 000.
• 1 ≤ a_i ≤ 10⁹.
• 1 ≤ m ≤ 100 000.
• 1 ≤ l_i ≤ r_i ≤ n.
• Suma wartości n oraz suma wartości m we wszystkich przypadkach testowych nie przekroczą 2 ⋅ 10⁵.

Przykład

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

-1
3