← 返回题目列表

Codeforces · 377/B

B. 准备比赛

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

马上就要举行世界上最大的编程大赛了,但是测试系统还有m个bug。比赛主办方是一所知名大学,无奈之下只能吸引大学生来修复所有的bug。这所大学有n名学生能够完成这样的工作。学生们意识到他们是组织者的唯一希望,所以他们不想免费工作:第 i 个学生希望在他的科目中获得 ci“通行证”(无论他的作业量有多大)。

Bug 和学生一样,是不一样的:每个 Bug 的特点是复杂性 aj,每个学生都有他的能力水平 bi。学生i只有在其能力水平不低于bug的复杂度bi≥aj时才能修复bug j,并且他在一天内完成。否则,该错误将必须由另一名学生修复。当然,没有一个学生能够在一天之内解决几个错误。所有错误都不相互依赖,因此可以按任何顺序纠正它们,并且不同的学生可以同时工作。

大学希望尽快修复所有错误,但给学生的总次数不超过 s 次。确定使用哪些学生来完成此任务,并制定工作计划,说明哪个学生应该修复哪个错误。

输入

第一行包含三个空格分隔的整数:n、m 和 s(1 ≤ n、m ≤ 105、0 ≤ s ≤ 109)——学生人数、系统中的错误数量以及大学准备给学生的最大通过数。

下一行包含 m 个空格分隔的整数 a1, a2, ..., am (1 ≤ ai ≤ 109) - bug 的复杂性。

下一行包含 n 个空格分隔的整数 b1, b2, ..., bn (1 ≤ bi ≤ 109) - 学生的能力水平。

下一行包含 n 个空格分隔的整数 c1, c2, ..., cn (0 ≤ ci ≤ 109) - 学生希望获得帮助的通过数。

输出

如果大学无法纠正所有错误,请打印“NO”。

否则,在第一行打印“YES”,并在下一行打印m个空格分隔的整数:这些数字中的第i个应该等于最佳答案中纠正第i个错误的学生的数量。应尽快纠正错误(必须花费最少的天数),并且给定的总通过次数不得超过 s。如果有多个最佳答案,则可以输出其中任何一个。

示例

输入 #1

3 4 9
1 3 1 2
2 1 3
4 3 6

输出 #1

YES
2 3 2 3

输入 #2

3 4 10
2 3 1 2
2 1 3
4 3 6

输出 #2

YES
1 3 1 3

输入 #3

3 4 9
2 3 1 2
2 1 3
4 3 6

输出 #3

YES
3 3 2 3

输入#4

3 4 5
1 3 1 2
2 1 3
5 3 6

输出#4

NO

注意

考虑第一个样本。

第三个学生(级别 3)必须修复第二个和第四个错误(相应的复杂度为 3 和 2),第二个学生(级别 1)必须修复第一个和第三个错误(它们的复杂度也等于 1)。修复每个错误每个学生需要一天的时间,因此修复所有错误需要 2 天(学生可以并行工作)。

第二个学生想要 3 个通行证来帮助他,第三个学生想要 6 个通行证。它符合大学的能力,因为它准备最多给予 9 个通过。