Opis

Jasiu jest niegrzecznym chłopcem i bardzo lubi imprezować. Akurat tak się dobrze dla niego złożyło, że jego rodzice wyjechali z domu na dłużej, więc dzień w dzień organizuje u siebie imprezki (biedni sąsiedzi… nie wyśpią się). Po którymś dniu zabawy z rzędu Jasiu obudził się o godzinie 5:30 (oczywiście po południu), z nieodłącznym bólem głowy. Jakiś czas później zorientował się, że nie ma pieniędzy na zorganizowanie kolejnej, już zapowiedzianej, imprezy. Po kilku minutach ciężkiego i bolesnego namysłu Jasiu wpadł na pomysł, że przecież może oddać do punktu skupu tak licznie zgromadzone butelki, walające się po całym domu. Zostało już niewiele czasu (skup zamykają o 6:00), więc chłopiec nie może na raty oddawać butelek. Zdąży tylko raz dojść do skupu, stąd musi od razu zapakować butelki do plecaka tak, by uzyskać możliwie największą kwotę pieniędzy za nie. [ Dzieci, nie róbcie tego same w domu! ]

Butelki zebrane przez Jasia są bardzo różnorodne. Każda może być scharakteryzowana przez wartość (kwotę, którą oferuje skup butelek), ciężar oraz kolor (jest 5 różnych kolorów) — potencjalnie każda butelka może być inna. Ciężar butelek jest o tyle ważny, że Jasiu w tym stanie ma ograniczony udźwig — jest to jedyny element, który ogranicza chłopca (plecak jest raczej mocny i duży, więc można przyjąć, że pomieściłby wszystkie butelki). Z kolei na podstawie koloru punkt skupu może przyznać zwyżkę. Polega to na tym, że dla każdego koloru podane są dwa progi T1 i T2 oraz dwie wartości B1 i B2. Jeżeli chłopiec przyniesie co najmniej T2 butelek danego koloru, to za każdą butelkę tegoż koloru dostanie o B2% więcej pieniędzy niż zapłaciłby normalnie. Natomiast jeśli przyniesie co najmniej T1 (ale mniej niż T2), to skup za każdą butelkę tegoż koloru zapłaci o B1% więcej. Jeżeli butelek danego koloru będzie mniej niż T1 to zwyżki za ten kolor nie będzie.

Zadanie

Dane są informacje o butelkach zebranych przez Jasia, maksymalny łączny ciężar jaki chłopiec może udźwignąć oraz informacje o zwyżkach udzielanych w punkcie skupu butelek. Na ich podstawie należy wyliczyć jaka jest największa możliwa kwota, jaką Jasiu może uzyskać.

Specyfikacja wejścia

Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę zestawów danych. Pierwsza linia każdego zestawu danych zawiera dwie liczby całkowite N i M (1 ≤ N ≤ 75, 1 ≤ M ≤ 1000), oznaczające odpowiednio liczbę butelek oraz maksymalny udźwig Jasia. Następne pięć linii zestawu zawiera cztery liczby całkowite, opisujące zwyżki dla każdego z pięciu kolorów: T1, B1, T2 i B2 (1 ≤ T1 ≤ T2 ≤ 100 oraz 0 ≤ B1 ≤ B2 ≤ 1000). Kolejne N linii zestawu zawiera opisy butelek, każdy składający się z trzech liczb całkowitych V, W i C (1 ≤ V ≤ 10000, 1 ≤ W ≤ M oraz 1 ≤ C ≤ 5), oznaczających odpowiednio wartość podstawową, ciężar oraz kolor butelki.

Specyfikacja wyjścia

Dla każdego zestawu należy zapisać, w osobnej linii, jedną liczbę rzeczywistą, będącą maksymalną kwotą, którą Jasiu może uzyskać, podaną z dokładnością do dwóch miejsc po przecinku.

Przykład

Wejście

2
3 10
1 100 100 1000
1 0 2 1000
1 2 3 4
3 4 5 6
5 6 7 8
1 5 2
10 3 1
1 4 2
5 4
1 5 3 1000
2 50 3 100
1 0 3 1000
2 4 3 1000
1 10 3 100
5 1 1
7 1 2
6 1 3
8 1 4
4 1 5

Wyjście

22.00
26.25