logo AlgoBeat OnlineJudge
登录 注册

#101713. [BZOJ 1713] [Usaco2007 China]The Bovine Accordion and Banjo Orchestra 音乐会

内存限制:64 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

FJ 的 头奶牛准备举办一场音乐会。其中 头奶牛是手风琴手,另外 头奶牛是班卓琴手,每个手风琴手有一个天才指数 ,每个班卓琴手也有一个天才指数 。 FJ 需要给手风琴手和班卓琴手配对。让第 位手风琴手和第 位班卓琴手配对,能产生 的收益。 不幸的是,FJ 的奶牛都存在一种怪癖:如果第 位手风琴手和第 位班卓琴手配对,那么第 位手风琴手,不会选择与第 位班卓琴手配对。这给 FJ 的配对计划带来了很多不便。 更糟糕的是,那些失去演出机会的失落的奶牛,为了消解内心的失落感情,会成群结队地到酒吧喝酒。 如果第 号手风琴手到第 号手风琴手都是失落的( 号手风琴手不存在或是参加了演出),这些奶牛就会去结队去酒吧喝酒,开销为:

对于班卓琴手,也有类似的规律。 现在 FJ 不得不好好考虑下他的计划了,他想让你算出他的最大的收益。

输入格式

第一行一个整数 。接下来 行,每行一个整数 。接下来 行,每行一个整数

输出格式

输出 FJ 能获得的最大收益。

样例

样例输入 #1

3
1
1
5
5
1
1

样例输出 #1

17

样例说明

手风琴手 和班卓琴手 搭配,收益 。 手风琴手 一块喝酒,花费 。 班卓琴手 一块喝酒,花费 。 最终收益为

数据范围与提示

对于 的数据,。 Gold