동전 줄

양의 정수 값을 가지는 동전 $n$개가 한 줄로 놓여 있다. 각 동전의 값은 $c_1, c_2, \dots, c_n$이며 서로 같을 수도 있다. 인접한 두 동전을 동시에 고를 수 없다는 제약 아래에서, 고른 동전들의 값의 합을 최대로 만들어라.

첫 번째 줄에는 이어지는 동전 줄의 개수를 나타내는 양의 정수 $n$이 주어진다. 다음 $n$개의 줄에는 각각 하나의 동전 줄이 주어지며, 하나 이상의 공백으로 구분된 양의 정수들의 목록이다. 한 줄에 놓인 동전은 최대 20개이다.

각 동전 줄에 대해, 인접한 두 동전을 동시에 고르지 않는다는 제약 아래에서 얻을 수 있는 값의 합의 최댓값을 한 줄에 하나씩 출력한다. 각 답은 별도의 서식 없이 양의 정수로만 출력한다.