W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
W Bajtogórach znajduje się kurort narciarski Bajtyrk słynący z narciarskich tras biegowych. Są one bardzo malownicze, gdyż część z nich jest położona wysoko w górach lub w trudno dostępnych miejscach. Użytkownicy tras często korzystają z wyciągów ułatwiających dotarcie do niektórych z nich. Każdy wyciąg i każda trasa zaczyna się i kończy na określonej polanie. Trasy narciarskie nie mogą się przecinać, ale mogą przebiegać naturalnymi skalnymi tunelami i estakadami.
Trasy narciarskie mogą być jednokierunkowe lub dwukierunkowe. Podobnie, niektóre wyciągi (kolejki linowe) mogą być jedno lub dwukierunkowe.
Za korzystanie z wyciągów płaci się kartą magnetyczną. Karty kupuje się w kasach. Każda karta zawiera określoną liczbę punktów. Skorzystanie z każdego z wyciągów wiąże się z utratą pewnej liczby punktów zależnej od wyciągu. Niestety kasy nie zwracają pieniędzy za niewykorzystane punkty.
Bajtoni jest dziś na nartach ostatni dzień. Została mu jedna karta z pewną liczbą punktów, które chciałby wykorzystać do maksimum. Możesz założyc, że ta liczba punktów wystarczy na powrót do Bajtyrku.
Napisz program, który:
W pierwszym wierszu standardowego wejścia zapisane są dwie dodatnie liczby całkowite i , , oddzielone pojedynczym odstępem, oznaczające odpowiednio liczbę wszystkich polan oraz liczbę tych polan, które znajdują się na dole w samym Bajtyrku (są to polany o numerach od do włącznie).
W drugim wierszu zapisana jest jedna dodatnia liczba całkowita , , równa łącznej liczbie wszystkich tras narciarskich. Każdy z kolejnych wierszy zawiera po dwie różne dodatnie liczby całkowite, pooddzielane pojedynczymi odstępami, . Liczby te oznaczają numer początkowej i końcowej polany danej trasy narciarskiej. Trasy dwukierunkowe są tu liczone dwukrotnie i reprezentowane w pliku wejściowym przez dwa (niekoniecznie kolejne) wiersze (postaci " " i " ").
W -cim wierszu zapisana jest jedna dodatnia liczba całkowita , , równa liczbie wszystkich wyciągów. W kolejnych wierszach opisane są wyciągi. W każdym z tych wierszy zapisane są trzy dodatnie liczby całkowite , i , pooddzielane pojedynczymi odstępami. Liczby i oznaczają odpowiednio numer polany, na której wyciąg się zaczyna i numer polany, na której się kończy, . Liczba jest równa liczbie punktów, które trzeba zapłacić za przejazd wyciągiem, . Wyciągi dwukierunkowe (kolejki linowe) są tu liczone dwukrotnie i reprezentowane w pliku wejściowym przez dwa (niekoniecznie kolejne) wiersze (postaci " " i " "). Ceny przejazdu wyciągiem w jedną i w drugą stronę mogą być różne.
W ostatnim wierszu zapisane są dwie dodatnie liczby całkowite i , oddzielone pojedynczym odstępem, , . Pierwsza z nich oznacza numer polany, na której znajduje się Bajtoni a druga jest równa liczbie punktów na jego ostatniej karcie magnetycznej.
Twój program powinien zapisać w pierwszym (i jedynym) wierszu standardowego wyjścia jedną liczbę całkowitą, równą najmniejszej możliwej liczbie punktów, z jaką Bajtoni może wrócić do Bajtyrku.
Dla danych wejściowych:
5 2 6 3 2 3 5 1 5 3 4 1 2 4 3 4 3 1 1 4 3 5 5 2 2 3 4 5 4 9
Dla danych wejściowych:
1
Autor zadania: Marcin Sawicki.