422. House Robber

0

Easy

As a professional robber, your goal is to rob houses along a street. However, there is a security system that will alert the police if two adjacent houses are broken into on the same night. Given an array of integers representing the amount of money in each house, your task is to determine the maximum amount of money you can rob tonight without triggering the security system.

Input Format

The input starts with an integer N, representing the size of the array. The next line contains N space-separated integers, describing the money in each house.

Output Format

Print the maximum amount of money you can rob tonight without alerting the police.

Example

Input

5 2 7 9 3 1

Output

12

Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 400
Loading...

View Submissions

Console