F - Księżycowa wycieczka

Gdy na księżycu powstała kolonia badawcza firma Nadesico rozpoczęła organizowanie wycieczek. Prezesi chcieliby, żeby każda grupa wracała na Ziemię jak najbardziej zadowolona, aby rozreklamować te niecodzienne wakacje. Każda grupa ustala które atrakcje chciałaby zwiedzić, jednak często chcieliby oni zobaczyć więcej niż są w stanie podczas krótkiej wycieczki. Kolejnym problemem jest ograniczona ilość tlenu jaką można ze sobą zabrać na wyprawę poza bazę. Z tych powodów po zwiedzeniu każdej atrakcji, trzeba zawsze wrócić do centrum. Twoim zadaniem jest wybranie tych spośród wskazanych atrkacji, które najbardziej zadowolą zwiedzających.

Wejście

W pierszej linii znajduje sie jedna liczba naturalna N oznaczająca liczbę zestwów danych.
W opisie każdego zestawu pierwsza linia zawiera dwie liczby naturalne K i M oddzielone spacją, oznaczające odpowiednio czas przeznaczony na wycieczkę oraz liczbę atrakcji (0 < K <= 500; 0 < M <= 500). W kolejnych M wierszach znajdują się po dwie liczby naturalne A i B oddzielone spacją, opisujące kolejne atrakcje, oznaczające odpowiednio czas potrzebny na jej zwiedzenie (czas dojazdu+zwiedziania+powrotu) oraz jej atrakcyjność (0 < A <= 500; 0 < B <= 100).

Wyjśćie

Dla każdego zestawu należy wypisać jedną liczbę w wierszu oznaczającą sumę atrakcyjności dla najatrakcyjniejszego planu zwiedzania..

Przykładowy test

Dla wejścia:
2
7 2
8 5
10 12
5 3
2 4
3 9
4 16

Poprawną odpowiedzią jest:
0
16