Wstęp do programowania w C++

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 t_p, t_k (1 ≤ t_p < t_k ≤ 10⁹) 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.