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

Zadanie I - Podróże pana Jana - pakowanie

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 wi, ci (1 ≤ wi, ci ≤ 1000) określające maksymalny udźwig oraz koszt torby danego typu. W ostatniej linii znajduje się N liczb (1 ≤ Ti ≤ 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

Wejście

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

Wyjście

40
19
30