Problem Brief

Women in STEM Charity

Stacey is coordinating a beach clean-up event with her university's Women in STEM charity branch. The beach is covered with tin cans of varying weights arranged in a single line, indexed from 0 to n-1.

Stacey uses a scooper that can pick up three adjacent cans at a time. For each selection:

She identifies the lightest remaining can with weight w

She uses the scooper to pick up that can along with its two adjacent cans (or fewer if at the edge)

She continues this process until there are no cans left on the beach

If multiple cans have the lightest weight, Stacey selects the one with the smallest index. If a can has fewer than two adjacent cans, she removes the available adjacent cans.

Determine the sum of the weights of the lightest cans she picks in each selection.

Function Description

Complete the function findTotalWeight in the editor with the following parameters:

int cans[]: the weights of the cans on the beach

Returns

int: the sum of the minimum-weight cans at each selection

Constraints

3 ≤ length of cans ≤ 2000
1 ≤ cans[i] ≤ 10^5

1Example 1

Input

cans = [5, 4, 1, 3, 2]

Output

Explanation

Let there be n = 5 cans on the beach with weights represented by cans = [5, 4, 1, 3, 2].

First, choose the minimum weight, i.e., 1, and add that weight to the total. The cans with weights 4, 1, and 3 are removed. The array of cans is now [5, 2].

Then, choose the minimum weight, i.e., 2, and add that weight to the total. The cans with weights 2 and 5 are removed, and there are no more cans on the beach.

Hence, the total is 1 + 2 = 3.