Inwestycje

15.10.2010
Trudność

Inwestycje

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


Inwestowanie to poważna sprawa! Wie o tym doskonale pan Józef - ( znany z zadania Zalew ) przedsiębiorca z branży rolniczo-hodowlanej, który właśnie zabrał się za planowanie budżetu na nadchodzący rok 2011.

Pan Józef opracował listę inwestycji, które mógłby przeprowadzić w swoim gospodarstwie ( np. budowa elektrowni wiatrowej, nowej stodoły, stworzenie strony internetowej, wprowadzenie ekologicznych nawozów ), wraz z kosztem każdej z nich. 

Oczywiście, celem inwestowania jest osiąganie wysokich zysków. Pan Józef wie, że niektóre kombinacje wprowadzonych iwenstycji przyniosą mu bardzo konkretne zyski. Przykładowo:

  • Wprowadzenie ekologicznych nawozów oraz budowa elektrowni wiatrowej ( koniecznie obie jednocześnie! ) spowoduje przyznanie panu Józefowi nagrody dla najbardziej ekologicznego rolnika roku.
  • Budowa elektrowni wiatrowej pozwoli zaoszczędzić konkretną sumę na rachunkach za prąd.

( każda inwestycja, jak widać w powyższym przykładzie, może jednocześnie przyczynić się do osiągnięcia wielu rożnych zysków )

Wiedząc ile kosztuje każda z inwestycji, jaki przychód przyniesie każda z osiągniętych korzyści, oraz które inwestycje są wymagane do osiągnięcia każdej korzyści, oblicz maksymalny zysk ( suma przychodów z osiągniętych korzyści pomniejszona o sumę kosztów wprowadzonych inwestycji ) jaki może osiągnąć pan Józef w roku 2011.

Na liście możliwych do osiągnięcia korzyści mogą pojawić się takie, do których osiągnięcia nie są potrzebne żadne inwestycje.

Wejście

W pierwszej linii znajduje się jedna liczba naturalna Z ( 1 <= Z <= 10 ) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

W pierwszej linii zestawu znajdują się dwie liczby naturalne A i B ( 1 <= A, B <= 100 ). A oznacza liczbę inwestycji, B oznacza liczbę możliwych korzyści.

W drugiej linii zestawu znajduje się A liczb naturalnych ai ( 1 <= ai <= 1000000 ), gdzie ai oznacza koszt wprowadzenia i-tej inwestycji ( inwestycje numerujemy od 1 do A ).

W trzeciej linii zestawu znajduje się B liczb naturalnych bi ( 1 <= bi <= 1000000 ), gdzie bi oznacza zysk z i-tej korzyści ( korzyści numerujemy od 1 do B ).

W czwartej linii zestawu znajduje się liczba naturalna K ( 1 <= K <= A*B ).

W K kolejnych liniach zestawu znajdują się po dwie liczby naturalne xi, yi oddzielone spacją ( 1 <= xi <= A, 1 <= yi <= B ). Taki zapis oznacza, że do osiągnięcia yi-tej korzyści niezbędne jest wprowadzenie xi-tej inwestycji.

Żadna para xi, yi nie pojawi się na wejściu dwukrotnie.

Wyjście

Dla każdego zestawu w osobnej linii należy wypisać maksymalny możliwy do osiągnięcia zysk.

Przykład

Wejście Wyjście

1
3 4
10 20 10
5 30 5 5
4
1 1
1 2
2 2
3 3

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

Organizatorzy:

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com