← 返回题目列表

Codeforces · 1076/F

F. 暑期实践报告

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

Vova 今年已经参加了夏季训练,现在他应该写一份关于训练进展情况的报告。

Vova已经画好了所有的表格,写下了所有的公式。此外,他已经决定报告将由$$$n$$$页组成,第$$$i$$$页将包括$$$x_i$$$表格和$$$y_i$$$公式。页码从 $$$1$$$ 到 $$$n$$$。

Vova 一页接一页地填充页面,在完成页 $$$i$$$ 之前他无法填充页 $$$i + 1$$$ 并且他无法跳过页面。

但是,如果他连续绘制严格超过 $$$k$$$ 表格或连续严格写入超过 $$$k$$$ 公式,那么他会感到无聊。 Vova 希望重新排列每一页中的表格和公式,这样他就不会在这个过程中感到无聊。 Vova 无法将某些表格或某些公式移动到另一页。

请注意,计数不会在新页面开始时重置。例如,如果页面以 $$$3$$$ 表结尾,下一页以 $$$5$$$ 表开始,则将其计为连续 $$$8$$$ 表。

帮助 Vova 确定他是否可以重新排列每页上的表格和公式,使得一行中不超过 $$$k$$$ 个表格,并且一行中不超过 $$$k$$$ 个公式。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le k \le 10^6$$$)。

第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le 10^6$$$) — 第 $$$i$$$ 页上的表格数量。

第三行包含 $$$n$$$ 整数 $$$y_1, y_2, \dots, y_n$$$ ($$$1 \le y_i \le 10^6$$$) — 第 $$$i$$$ 页上的公式数量。

输出

如果 Vova 可以重新排列每页上的表格和公式,使得一行中不超过 $$$k$$$ 个表格且一行中不超过 $$$k$$$ 个公式,则打印“YES”。

否则打印“NO”。

示例

输入 #1

2 2
5 5
2 2

输出 #1

YES

输入 #2

2 2
5 6
2 2

输出 #2

NO

输入 #3

4 1
4 1 10 1
3 2 10 1

输出 #3

YES

注意

在第一个示例中,重新排列所有内容的唯一选项如下(令表为“T”,公式为“F”):

- 页$$$1$$$:“TTFTTFT”
- 页$$$2$$$:“TFTTFTT”

这样所有表块的长度都是$$$2$$$。

在第二个示例中,无法以这样的方式拟合所有内容,使得一行中不超过 $$$2$$$ 表和一行中不超过 $$$2$$$ 公式。