Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWP8_2F - Spotkania

Jesteś kierownikiem projektu w jednej z korporacji. Większość dnia spędzasz na spotkaniach. Niestety często bywa tak, że zebrania nakładają się na siebie i nie możesz być na każdym z nich.

Dzisiaj w Twojej firmie ma się odbyć dokładnie n spotkań. Znasz czas rozpoczęcia i zakończenia każdego z nich. Zaplanuj swój dzień tak, aby być na jak największej liczbie zebrań. W każdym spotkaniu, na które się wybierasz, musisz uczestniczyć od początku do końca. Jeżeli istnieje kilka możliwych rozwiązań wybierz to o najdłuższym łącznym czasie trwania zebrań. Zakładamy, że czas potrzebny na przejście z jednego spotkania na drugie jest nieznaczący, a zatem jeżeli jakieś spotkanie zaczyna się w tym samym momencie gdy kończymy poprzednie to na pewno na nie zdążymy.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita t ∈ [1;10] określająca liczbę zestawów danych. W kolejnych wierszach podane są zestawy danych. W pierwszej linii każdego zestawu danych znajduje się jedna liczba całkowita n ∈ [1;1000] oznaczająca liczbę zaplanowanych spotkań. W kolejnych n liniach znajdują się po dwie liczby naturalne tp, tk (1 ≤ tp < tk ≤ 109) określające odpowiednio czas rozpoczęcia i czas zakończenia spotkania.

Wyjście

Na wyjściu należy wypisać maksymalną liczbę spotkań w jakich możemy wziąć udział oraz sumaryczny czas ich trwania.

Przykład

Wejście

1
6
1 5
5 11
2 4
4 5
5 7
10 11

Wyjście

4 6

Wyjaśnienie do przykładu

Najlepszym wyborem jest uczestniczenie w spotkaniach: 2-4, 4-5, 5-7 i 10-11.


Dodane przez:Maciej Boniecki
Data dodania:2016-03-18
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Pochodzenie:VIII Mistrzostwa WWSI w Programowaniu

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.