跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F2458. Yaroslav and Sequence

  • ID: 2464
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:进阶
  • 上传者:
  • 构造
  • 算法思想
  • 进阶
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Yaroslav and Sequence

题目描述

A. Yaroslav and Sequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yaroslav has an array, consisting of (2·n-1) integers. In a single operation Yaroslav can change the sign of exactly n elements in the array. In other words, in one operation Yaroslav can select exactly n array elements, and multiply each of them by -1.

Yaroslav is now wondering: what maximum sum of array elements can be obtained if it is allowed to perform any number of described operations?

Help Yaroslav.

Input

The first line contains an integer n (2≤n≤100). The second line contains (2·n-1) integers − the array elements. The array elements do not exceed 1000 in their absolute value.

Output

In a single line print the answer to the problem − the maximum sum that Yaroslav can get.

Examples
Input
2
50 50 50
Output
150
Input
2
-1 -100 -1
Output
100
Note

In the first sample you do not need to change anything. The sum of elements equals 150.

In the second sample you need to change the sign of the first two elements. Then we get the sum of the elements equal to 100.


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 2091 题。保留原作者与原赛事署名。