#P14822. [ICPC 2023 Yokohama R] Liquid Distribution

[ICPC 2023 Yokohama R] Liquid Distribution

Description

经过多年的太空探索,人类成功地从一颗小行星上带回少量样本材料到地球!这些材料存储在几个瓶子中,每个瓶子都装着液体 A 和液体 B 的完全混合物。

经过激烈讨论,最终达成一致:所有带回的材料应分发给参与探索的研究机构。根据每个机构的研究主题,确定了需要发送的液体 A 和 B 的量。

然而,在这个决定之后,发现了一个问题:以目前的人类技术,无法将两种液体从混合物中分离出来。我们能执行的操作仅包括从一个或多个瓶子中取出一定量的混合物,并将它们倒入一个新瓶子中混合。

你的任务是判断约定的液体分配方案是否可能实现。

Input Format

输入由单个测试用例组成,格式如下。

$$\begin{aligned} & n \ m \\ & a_1 \ \cdots \ a_n \\ & b_1 \ \cdots \ b_n \\ & c_1 \ \cdots \ c_m \\ & d_1 \ \cdots \ d_m \\ \end{aligned}$$

其中,nn 是最初装有液体 A 和液体 B 混合物的瓶子数量,mm 是要接收液体的研究机构数量。nnmm 均为正整数,且不大于 500500。接下来的两行每行包含 nn 个整数,表示第 ii 个瓶子 (1in1 \leq i \leq n) 最初含有 aia_i 毫升的液体 A 和 bib_i 毫升的液体 B 的混合物。再接下来的两行每行包含 mm 个整数,表示需要发送给第 jj 个机构 (1jm1 \leq j \leq m) 的瓶子应含有 cjc_j 毫升的液体 A 和 djd_j 毫升的液体 B。所有 aia_ibib_icjc_jdjd_j 均为不大于 10610^6 的正整数。同时满足 i=1nai=j=1mcj\sum_{i=1}^{n} a_i = \sum_{j=1}^{m} c_ji=1nbi=j=1mdj\sum_{i=1}^{n} b_i = \sum_{j=1}^{m} d_j

Output Format

如果约定的分配方案可能实现,则输出 Yes;否则,在一行中输出 No

2 2
1 3
3 1
2 2
1 3
Yes
2 2
2 2
2 2
1 3
3 1
No
3 5
2 5 8
3 5 7
3 3 3 3 3
3 3 3 3 3
Yes
3 2
4 4 4
1 9 5
6 6
2 13
No

Hint

对于样例输入 1,符合决策的唯一方案是:从瓶子 1 中取 0.50.5 毫升,从瓶子 2 中取 2.52.5 毫升,将它们混合在一个瓶子中发送给机构 1,并将剩余的混合物装在另一个瓶子中发送给机构 2。

对于样例输入 2,分配协议无法实现。