Problem description

Back
Show PDF
Zarządzaj swoją energią
(A)
Limit pamięci: 256 MB
Limit czasu: 2.00 s

Bajtazar ma bardzo napięty kalendarz. Ciężko pracował, aby wszystko zaplanować i upewnić się, że aktywności się nie nakładają. Teraz jest poranek i martwisz się, że mimo całego entuzjazmu Bajtazarowi może zabraknąć energii.

Na początku dnia Bajtazar zaczyna z planem N aktywności oraz pełnym zapasem E jednostek energii. Aktywności muszą być wykonywane w kolejności 1, …, N, a energia nie może spaść poniżej 0 ani przekroczyć E (wszelka nadwyżka ponad E przepada).

Podczas dnia każda aktywność może zużyć nieujemną liczbę całkowitą jednostek energii wybraną przez Bajtazara. Niezależnie od tego, ile jednostek energii Bajtazar włożył w aktywność, po jej zakończeniu odzyskuje R jednostek energii (lub mniej, jeśli energia miałaby przekroczyć limit E).

Praca wykonana przez Bajtazara dla aktywności i jest równa liczbie poświęconych jej jednostek energii pomnożonej przez wartość aktywności vi. Aby obliczyć pracę wykonaną przez Bajtazara podczas całego dnia, należy zsumować pracę dla każdej aktywności.

Pomóż Bajtazarowi zarządzać energią podczas dnia tak, aby łączna wykonana przez niego praca była jak największa.

Wejście

W pierwszym wierszu wejścia znajduje się liczba testów T. Następnie podanych jest T testów.

Każdy test składa się z dwóch wierszy.

W pierwszym wierszu są trzy liczby całkowite: maksymalna (i początkowa) liczba jednostek energii E, liczba jednostek energii R odzyskiwana po każdej aktywności oraz liczba aktywności w planie dnia N.

W drugim wierszu jest N liczb całkowitych vi, opisujących wartości kolejnych aktywności.

Wyjście

Dla każdego testu wypisz w osobnym wierszu największą pracę, jaką może wykonać Bajtazar, odpowiednio zarządzając energią w ciągu dnia.

Ograniczenia

1 ≤ T ≤ 100, 1 ≤ N ≤ 10 000, 1 ≤ E, R, vi ≤ 107

Podzadania

Podzadanie Warunki Punkty
1 1 ≤ E ≤ 5, 1 ≤ R ≤ 5, 1 ≤ N ≤ 10, 1 ≤ vi ≤ 10 10
2 vi ≤ vj dla i ≤ j innymi słowy, ciag v_i jest niemalejący 10
3 1 ≤ E ≤ 1000, 1 ≤ N ≤ 1000, suma N+E we wszystkich testach  ≤ 20 000 30
4 Brak dodatkowych ograniczeń 50

Przykład

Wejście Wyjście Wyjaśnienie 
3
5 2 2
2 1
5 2 2
1 2
3 3 4
4 1 3 5

12
12
39
  • W pierwszym przypadku możemy wydać całe 5 dżuli energii na pierwszą aktywność (zyskując 10), następnie odzyskać 2 dżule i wydać je na drugą aktywność.
  • W drugim przypadku wydajemy 2 dżule na pierwszą aktywność, odzyskujemy je, a następnie wydajemy 5 dżuli na drugą.
  • W trzecim przypadku tempo odzyskiwania energii jest równe maksymalnej energii, co oznacza, że po każdej aktywności zawsze odzyskujemy pełny zapas energii – więc możemy wydać pełne 3 dżule na każdą aktywność.