AlgoLiga 2018

Janusz znalazł poważną lukę w bankowości internetowej banku, w którym ma konto. Jest on w stanie modyfikować listę ostatnich 2×n-1 operacji. Dokładniej rzecz ujmując Janusz może zmienić typ dokładnie n wybranych z listy operacji. Zmiana typu polega na zamianie wypłaty na wpłatę i vice versa. Dodatkowo wyboru i zamiany n operacji Janusz może dokonywać wiele razy. Nasz bohater zastanawia się teraz jakie maksymalne saldo ostatnich 2×n-1 operacji mógłby uzyskać wykorzystując znalezioną przez siebie lukę?

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita n ∈ [1;500] określająca liczbę operacji jakie Janusz może zmienić za każdym razem. W kolejnej linii znajduje się 2×n-1 liczb całkowitych opisujących operacje bankowe. Ujemna liczba oznacza wypłatę pieniędzy z rachunku bankowego, zaś liczba dodatnia wpłatę. Wartość bezwzględna każdej z podanych kwot nie przekracza 10⁴. Żadna z kwot nie jest równa 0.

Wyjście

Na wyjściu należy wypisać maksymalne saldo ostatnich 2×n-1 operacji jakie Janusz mógłby uzyskać gdyby wykorzystał znaleziony błąd.

Przykład #1

Wejście

2
-400 -1000 -900

Wyjście

1500

Przykład #2

Wejście

2
500 -100 -5000

Wyjście

5600

Przykład #3

Wejście

5
-100 -100 -100 -100 -100 -100 -100 -100 -100

Wyjście

900

Wyjaśnienie do przykładu

Oto kolejne zamiany. W każdym kroku pogrubione zostały operacje, które uległy zmianie:

1. -100 -100 -100 -100 -100 -100 -100 -100 -100
2. 100 100 100 100 100 -100 -100 -100 -100
3. 100 100 100 100 -100 100 100 100 100
4. 100 100 100 -100 -100 -100 -100 -100 -100
5. 100 100 -100 100 100 100 100 -100 -100
6. 100 100 100 -100 -100 100 100 100 100
7. 100 100 100 100 -100 -100 -100 -100 -100
8. 100 100 100 100 100 100 100 100 100