Polish version    English version  
  Olympic camps


 News
 About Olympic
 History of OI
 OI books
 National team
 Olympic camps
III camp 2002
IV camp 2003
V camp 2005
VI camp 2005
 Photo gallery
 Links
 SIO
 MAIN
This document is not available in English version.

III Obóz im. A. Kreczmara 2002

Zadanie: c

C: Nauka programowania

dzień czwarty 9 sierpnia 2002
Plik źródłowy: c.??? (np. pas, c, cpp)
Plik wejściowy: c.in
Plik wyjściowy: c.out

Jasiu postanowił nauczyć się programować. W tym celu zapisał się na Internetowy Kurs Programowania. Na kursie jest do rozwiązania P zadań, ułożonych od najłatwiejszego do najtrudniejszego. System nie pozwala uczestnikom kursu rozwiązywać trudnych zadań, zanim nie zrobią tych prostych. Dokładniej, zawsze należy wybrać sobie do rozwiązywania jedno z K najłatwiejszych zadań spośród jeszcze nie rozwiązanych.

Każde zadanie wymaga określonej liczby sekund na rozwiązanie. Niekoniecznie trudniejsze zadanie wymaga więcej czasu na rozwiązanie niż łatwiejsze.

Jasiu może poświęcić na treningi F dni. Każdego dnia ma pewną ilość czasu, którą może poświęcić na rozwiązywanie zadań. Aby się nie przemęczać, Jasiu będzie każdego dnia rozwiązywał co najwyżej jedno zadanie. Nie będzie też rozwiązywał jednego zadania przez kilka dni (zawsze chce mieć tyle wolnego czasu, żeby skończyć zadanie tego samego dnia).

Zadanie

Napisz program, który:

  • wczyta liczbę zadań, liczbę minut potrzebną na rozwiązanie kolejnych zadań, liczbę K oraz opis wolnego czasu Jasia,
  • wyznaczy maksymalną liczbę zadań, którą Jasiu będzie w stanie rozwiązać,
  • zapisze wynik.

Wejście

W pierwszym wierszu pliku wejściowego c.in znajdują się trzy liczby oddzielone spacjami: liczba zadań P, liczba wolnych dni F oraz liczba K. 1 <= P <= 50000, 1 <= F <= 50000, 1 <= K <= P. Kolejnych P wierszy zawiera liczby T1...TP, 1 <= Ti <= 50000. Ti jest liczbą sekund potrzebną na rozwiązanie i-tego zadania z kolei. Następnych F wierszy zawiera liczby W1...WF, 1 <= Wi <= 50000. Wi jest ilością wolnego czasu (w sekundach) i-tego dnia.

Wyjście

W jedynym wierszu pliku wyjściowego c.out powinna znaleźć się jedna liczba - maksymalna liczba zadań, którą Jasiu może rozwiązać podczas treningu.

Przykład

Dla pliku wejściowego c.in:

2 2 1
100
50
75
200

poprawną odpowiedzią jest plik wyjściowy c.out:

1



Print friendly version