XI Wiosenny Turniej w Programowaniu Zespołowym Poznań, 26 maja 2007

Opis

Pan Jan bardzo lubi podróżować. Ostatnio zaplanował bardzo daleką podróż i ma wiele rzeczy do zabrania ze sobą. Chciałby spakować swoje rzeczy w torby, które sumarycznie kosztują jak najmniej. Sklep oferuje torby różnych typów. Torba danego typu może udźwignąć tylko określony ciężar i ma określoną cenę. Pomóż wybrać panu Janowi zestaw toreb, w które będzie mógł spakować wszystkie potrzebne rzeczy, a którego koszt będzie najmniejszy. Pan Jan może kupić dowolną liczbę toreb danego typu.

Specyfikacja wejścia

W pierwszej linii pliku wejściowego znajduje się liczba naturalna d (1 ≤ d ≤ 100), określająca liczbę zestawów danych.

Pierwsza linia każdego zestawu zawiera liczbę N (1 ≤ N ≤ 20), określającą liczbę rzeczy, które pan Jan planuje zabrać w podróż oraz liczbę M (1 ≤ M ≤ 50), określającą liczbę różnych typów toreb. W kolejnych M liniach każdego testu będą znajdować się pary liczby w_i, c_i (1 ≤ w_i, c_i ≤ 1000) określające maksymalny udźwig oraz koszt torby danego typu. W ostatniej linii znajduje się N liczb (1 ≤ T_i ≤ 1000), określających wagę poszczególnych elementów. Udźwig co najmniej jednej torby jest niemniejszy niż waga najcięższej rzeczy (na pewno istnieje rozwiązanie).

Specyfikacja wyjścia

Dla każdego zapytania wypisać minimalny koszt zestawu toreb.

Przykład

3
5 2
5 10
8 20
6 1 2 5 4
5 3
3 2
6 7
10 10
4 5 5 3 2
10 1
10 6
1 7 8 10 6 4 4 3 1 5

40
19
30