## LCC/Moose '18 Contest 3 J4 - Tall People 3

View as PDF

Points: 5
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Emily is a tall person! In fact, she is so tall, she wants to compete against her friend, MLE, to see who can grow the tallest! There are $$N$$ packets of growth hormones lined up in a line. The $$i^{th}$$ packet will cause the person who takes it to grow by $$k_i$$ metres. Each person will take turns taking the packets from the start of the line (Index $$1$$), starting with Emily first. They will alternate taking packets: Emily takes the first packet, MLE takes the second, Emily takes the third... etc.

Emily has a special trick up her sleeve, which she can use at most once. When she uses it, she will take two consecutive packets, meaning she will skip MLE's turn. After Emily takes the two consecutive packets, it will be MLE's turn. It will then alternate back and fourth as defined above.

Emily wants you to tell her what is the maximum amount she can grow, if she can use her trick at most once!

#### Input Specification

The first line will contain one integer, $$N\ (1 \le N \le 10^3)$$, the number of packets.

The second line will contain $$N$$ integers, $$k_1, k_2, \ldots, k_N\ (1 \le k_i \le 100)$$, meaning that taking the $$i^{th}$$ will cause the person to grow $$k_i$$ metres.

#### Output Specification

Output the maximum number of metres Emily can grow!

#### Sample Input 1

5
1 3 2 4 1

#### Sample Output 1

8

#### Sample Input 2

4
3 1 3 1

#### Sample Output 2

7

#### Explanation for Sample 2

Emily can take packets with index $$1$$ and $$3$$, and using her special trick, take packet with index $$4$$ for a total sum of:

$$k_1 + k_3 + k_4 = 3 + 3 + 1 = 7$$