P17892 [ICPC 2026 Nanchang I] Critical Perfect

题目描述

枫蜜正在挑战一款音乐游戏的高难关卡。关卡中有 $n$ 个按顺序下落的音符,第 $i$ 个音符的基础分值为 $a_i$。当玩家击中前 $i$ 个音符后,**累计得分** $s_i = \sum_{k=1}^i a_k$ 将决定连击特效的触发条件。 具体来说,第 $i$ 个音符有一个得分目标区间 $[l_i, r_i]$,只有 $s_i$ 落在该区间内,才能触发完美的连击特效演出,否则特效链会中断。 作为“区域增幅”道具的拥有者,枫蜜可以任意次使用该道具:每次使用可以**选择一段连续的音符** $[l, r]$,并将这些音符的基础分值全部增加 $1$。道具的使用次数会影响最终的关卡评分,因此枫蜜希望用最少的次数达成全程完美连击。 请你帮她计算,最少需要使用多少次区域增幅道具,才能让每个音符 $i$ 的累计得分 $s_i$ 都满足 $l_i \le s_i \le r_i$,或报告无解。

输入格式

有多组测试数据。第一行输入一个整数 $t$ ($1 \le t \le 5000$),表示测试数据组数。对于每组测试数据: 第一行包含一个整数 $n$ ($1 \le n \le 5000$),表示音符的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$),表示每个音符的基础分值。 接下来 $n$ 行,每行包含两个整数 $l_i$ 和 $r_i$ ($0 \le l_i \le r_i \le 10^{18}$),表示在第 $i$ 个音符击中后的累计得分目标区间。 保证所有测试数据的 $n$ 之和不超过 $5000$。

输出格式

对于每组测试数据,输出一个整数,表示最少道具使用次数。若无法达成目标,输出 $-1$。

说明/提示

对于样例的第一组数据,一种可行的操作方案如下:对区间 $[1,3]$ 使用 $4$ 次道具,原基础分值序列变为 $[10,6,12]$,累计得分为 $[10,16,28]$,满足条件。总操作次数为 $4$。可以证明不存在操作次数更少的方案。 对于样例的第二组数据,可以证明不存在可行的操作方案。