Fabryka butów

04.08.2010
Trudność

Fabryka butów

Limit czasowy: 1000 milisekund
Limit pamięciowy: 32000 kilobajtów


Pan Józef zainwestował ostatnio w fabrykę butów. Fabryka świetnie prosperuje choć, jak wie każdy przedsiębiorca, nigdy nie jest tak dobrze żeby nie mogło być lepiej. Pan Józef postanowił sprawdzić jaka cena pary butów zapewni jego fabryce największy zysk.

Koszt produkcji pary butów wynosi K.

Badania rynku wskazały N elementowy ciąg liczb naturalnych A[]. A[i] ( 1 <= i <= N ) oznacza liczbę osób, która kupi buty z fabryki pana Józefa, jeśli będą kosztowały co najwyżej i.

Oblicz maksymalny zysk fabryki ( czyli różnicę pomiędzy wartością sprzedanych butów a kosztem ich produkcji ).

Wejście

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ).

Pierwsza linia pojedynczego zestawu testowego zawiera liczbę N i K ( 1 <= N, K <= 105 ). W drugiej lini znajduje się N liczb A[1],A[2],...,A[N] ( 0 <= A[i] <= 105).

Wyjście

Dla każdego zestawu testowego należy wypisać maksymalny zysk fabryki.

Przykła d

Wejście Wyjście

2
5 1
5 4 3 2 1
5 1
1 2 3 4 5

12
27

Wyjaśnienie: W zestawie pierwszym gdy cena wyniesie 3 to  buty kupi 6 osób, czyli zysk wyniesie 6 * 3 - 6 * 1 = 12. W zestawie drugim gdy cena wyniesie 4 to buty kupi 9 osób, czyli zysk wyniesie 9 * 4 - 9 * 1 = 27.

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
3.625
Twoja ocena: Brak Ocena: 3.6 (8 ocen)

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com