問題一覧 > 通常問題

No.2332 Make a Sequence

レベル : / AI推定難易度 : 2225 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 32
作問者 : dyktr_06 / テスター : firiexp phocom hikikomori sepa38 Seed57_cash
お気に入りにしたユーザー ProblemId : 9531 / 自分の提出
問題文最終更新日: 2023-05-26 23:09:17
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
MMA Contest 015 (順位表) の他の問題:

Problem Statement

You are given an integer sequence $A$ of length $N$ and integer sequences $B, C$ of length $M$.

There is also an empty sequence $S$, and you may perform the following operation until the length of the sequence becomes $M$.

  • Let $l$ be the length of the sequence $S$ before the operation. Choose an integer $k$ satisfying $1 \leq k \leq \min(M - l, N)$, and append the contiguous subarray $(A_1, A_2, …, A_k)$ to the end of the sequence $S$.
  • This operation costs $k \times C_l$.

Determine whether the sequence $S$ can be made equal to the sequence $B$ after the operations, and if it is possible, find the minimum cost.


Constraints

  • $1 \leq N, M \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^9$
  • $1 \leq B_i \leq 10^9$
  • $1 \leq C_i \leq 10^9$
  • All input values are integers.

Input

The input is given from standard input in the following format.

$N$ $M$
$A_1$ $A_2$ ... $A_N$ 
$B_1$ $B_2$ ... $B_M$ 
$C_0$ $C_1$ ... $C_{M - 1}$  

Output

Print on one line the minimum cost to make the sequence $S$ equal to the sequence $B$.

If it is impossible to make them equal, print $-1$.

Sample

Sample 1
Input
4 7
1 2 3 1
1 1 2 3 1 1 2
1 2 3 2 1 2 3
Output
12

For example, performing the operations in the following order is optimal.

  • Append $(1)$ to the sequence $S$. This costs $1 \times 1 = 1$.
  • Append $(1, 2, 3)$ to the sequence $S$. This costs $3 \times 2 = 6$.
  • Append $(1)$ to the sequence $S$. This costs $1 \times 1 = 1$.
  • Append $(1, 2)$ to the sequence $S$. This costs $2 \times 2 = 4$.
Sample 2
Input
3 4
1 3 2
1 3 1 2
1 1 1 1
Output
-1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。