← 返回题目列表

AtCoder · agc054_f

F. 减量

中文机器翻译题面 查看原题

分数: 1800 点

问题陈述

给定的是一个序列 A of N 正整数和序列 B of N-1 正整数。 您可以多次执行以下操作。

  • 选择整数 i 和 j (1 \leq i < j \leq N)并将以下每个值减少 1: A_i,A_j,B_i,B_{i+1},\cdots,B_{j-1}。这里,此操作后不应有任何负值。

让 m 是可以完成的最大操作数。 求模数 998244353,序列 A 可以在之后 m 操作。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_{N-1}

输出

打印答案。


示例输入 1

3
1 2 2
1 2

示例输出 1

3

我们有 m=2。经过两次手术后, A 将是以下三个序列之一。

  • A=(1,0,0):我们在操作后得到这个 (i,j)=(2,3) 和 (i,j)=(2,3).
  • A=(0,1,0):我们在操作后得到这个 (i,j)=(1,3) 和 (i,j)=(2,3).
  • A=(0,0,1):我们在操作后得到这个 (i,j)=(1,2) 和 (i,j)=(2,3).

示例输入 2

4
1 1 1 1
2 2 2

示例输出 2

1

请注意,我们不区分具有不同内容的两个场景 B 如果内容 A 是相同的。


示例输入 3

4
2 2 3 4
3 1 4

示例输出 3

3