#P18092. Deletion Game

Deletion Game

Deletion Game

题目描述

有一个长度为 nn 的整数序列 SS,第 ii 个元素的权重为 aia_i。

先选择正整数 mm,把序列及其权重一起复制成 mm 份并首尾拼接。随后可以进行任意次(也可以零次)消除操作:

选择当前序列中的两个下标 i<ji<j,要求两处元素值相同。删除第 i+1i+1 至第 jj 个元素及对应权重,保留第 ii 个元素;剩余元素按原顺序重新紧密排列。

求剩余元素权重总和的最小值,并求达到这一最小值所需的最小副本数 mm。两个目标按先权重总和、后副本数的顺序优化。

输入格式

第一行一个整数 nn。第二行 nn 个整数 S1,…,SnS_1,\ldots,S_n。第三行 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

输出一行两个整数,依次为最小权重总和和最小副本数。

数据范围

1≤n,Si,ai≤3×1051\le n,S_i,a_i\le3\times10^5。

样例 1

输入

6
1 1 4 5 1 4
1 9 1 9 8 10

输出

2 1