P17503 [ICPC 2026 Wuhan I] Deletion Game

Yachiyo has an integer sequence $S$ of length $n$, and each position in the sequence (indexed from $1$) has a weight $a_i$. She can copy this sequence together with its weights and concatenate the copies end to end several times. Specifically, if she chooses to concatenate $m$ copies in total ($m \ge 1$), she will obtain a new sequence $S'$ of length $m\times n$ and a corresponding new weight sequence $a'$. For any $0 \le c

The input contains three lines. The first line contains an integer $n$ ($1 \le n \le 3\times10^5$), the length of the initial sequence $S$. The second line contains $n$ integers $S_1,S_2,\cdots,S_n$ ($1 \le S_i \le 3\times10^5$), representing the elements of the initial sequence $S$. The third line contains $n$ integers $a_1,a_2,\cdots,a_n$ ($1 \le a_i \le 3\times10^5$), representing the weight of each position.

Output one line containing two integers separated by a space: - The first integer is the minimum possible sum of weights of the remaining sequence after the operations. - The second integer is the minimum total number of copies of the original sequence needed to achieve that minimum weight sum.

In this sample, the optimal strategy is to use only $1$ copy of the original sequence (that is, $m=1$, with no extra copying). The initial sequence $S'$ is $[1,1,4,5,1,4]$, and the corresponding weight sequence $a'$ is $[1,9,1,9,8,10]$. Yachiyo can perform the following two operations: 1. Choose $i=1,j=2$ (at this time $S'_1=S'_2=1$), and delete the $(i+1)$-th through $j$-th elements (that is, delete the 2nd element). After the operation, $S'$ becomes $[1,4,5,1,4]$, and $a'$ becomes $[1,1,9,8,10]$. 2. In the new sequence, choose $i=2,j=5$ (at this time $S'_2=S'_5=4$), and delete the $(i+1)$-th through $j$-th elements (that is, delete the 3rd, 4th, and 5th elements). After the operation, the remaining $S'$ is $[1,4]$, and the remaining $a'$ is $[1,1]$. At this point, no further elimination is possible, and the sum of the remaining weights is $1+1=2$. It can be proved that under any number of copies and any sequence of operations, the weight sum cannot be smaller than $2$.