#mx8ba4. 黑客

黑客

题目背景

黑客梦梦有机会参加黑客比赛。比赛中,梦梦与熊熊对抗,目标是黑掉环状连接的计算机。操作规则如下:

梦梦首先操作,之后双方交替操作。

  • 梦梦首次操作可以选择任意计算机进行黑掉。
  • 熊熊首次操作可以选择任意未被黑掉的计算机进行保护。

后续操作中,梦梦可以:

  • 什么都不做,或
  • 黑掉未被黑掉且与被黑计算机直接相连的计算机。

后续操作中,熊熊可以:

  • 什么都不做,或
  • 保护未被黑掉且与被保护计算机直接相连的计算机。

如果连续两轮双方都选择不操作,游戏结束。初始状态:所有计算机既未被黑掉也未被保护。

每台计算机有一个价值,梦梦通过黑掉计算机获得相应分数。梦梦需要一个程序来计算他的最大可能得分,假设熊熊采取最佳策略。

输入格式

输入的第一行包含一个正整数n,表示计算机台数。

第二行是一个n个正整数的序列viv_iviv_i表示计算机i上存储的数据价值。

输出格式

一行一个整数,表示梦梦获得的最大可能得分。

数据范围

对于所有数据满足,2n,1vi21032\leq{n},1\leq{v_i}\leq{2*10^3}

对于20%的数据,n300n\leq{300}

对于60%的数据,n5103n\leq{5*10^3}

对于100%的数据,n5105n\leq{5*10^5}

样例

4
7 6 8 4
13
5
1 1 1 1 1
3

时间空间限制

1000ms,262144K