1009. 今晚吃草莓

题目描述

Celeste 山上有一个包含 $n$ 个位置的序列，位置从 $1$ 到 $n$ 编号。白井黑子需要依次进行 $m$ 次冲刺。

进行第 $i$ 次冲刺时，假设黑子当前位于位置 $p$。她可以选择整数位移 $d_i$，满足 $-k_i\le d_i\le k_i$。令 $q=p+d_i$：若 $q\le0$，则撞到左墙并停在位置 $1$；若 $q>n$，则撞到右墙并停在位置 $n$；否则停在位置 $q$ 且没有撞墙。特别地，恰好到达位置 $1$ 或 $n$ 不算撞墙。

如果 $|d_i|=k_i$，或者这次冲刺撞墙，则获得 $c_i$ 颗草莓；否则无法获取草莓。一次冲刺至多撞一次墙。

因为草莓糖分超标，所以白井黑子不希望获取太多草莓。现在给定起点 $s$，对于每个终点 $t=1,2,\ldots,n$，再给定草莓上限 $K_t$。白井黑子想要分别求从 $s$ 出发，恰好进行全部 $m$ 次冲刺，最终停在 $t$，且总获取的草莓数量不超过 $K_t$ 时，最多会撞墙多少次。各终点对应的过程互相独立。

输入格式

本题包含多组测试数据。

首先在第一行输入一个整数 $T$（$1\le T\le 200$）表示测试数据组数。

接下来对于每一组测试数据：

第一行包含三个整数 $n,m,s$（$1\le n,m\le500$，$1\le s\le n$），其中 $s$ 是起点。

第二行包含 $2m$ 个整数 $k_1,c_1,\cdots,k_m,c_m$（$1\le k_i\le n$，$1\le c_i\le10^9$）。

第三行包含 $n$ 个整数 $K_1,K_2,K_3,\cdots,K_n$（$0\le K_t\le\sum c_i$）。

保证所有测试数据的 $nm^2$ 之和不超过 $1.25\times10^8$。

输出格式

对于每一组测试数据，输出包含一行 $n$ 个整数。第 $t$ 个整数为终点 $t$ 对应的答案；若不存在合法方案，则输出 -1。

样例输入

1
5 4 3
3 2 5 4 2 1 4 3
0 2 5 7 10

样例输出

0 1 2 3 4

来源：2026杭电多校-测试专用（南外） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1235&pid=1009