U163893 [NOI2021SDPT2Test2]多项式时间哈密顿回路

这是一道多项式时间哈密顿回路题。 既然哈密顿回路已经属于 P 了，下面这道显然属于 P 的题需要给您来解决： 哈密顿回路是一个人。 哈密顿回路一共做了 $n$ 种 “QwQ”，第 $i$ 种 “QwQ” 有 $a_i$ 个。 她想让最少个数的**一种** “QwQ” 的个数最多。 你作为多项式时间复杂度要帮助哈密顿回路。 你可以创造 $m$ **个**任意种类的 "QwQ"，并且可以把一些变成另一些。 一个关系 $a\rightarrow b$ 意味着可以把任意个 $a$ 类型的 “QwQ” 变成 $b$ 类型的 “QwQ”。 一个 “QwQ” 可以被转换任意多次，从 $a$ 类型转换到 $b$ 类型然后转换到 $c$ 类型也是合法的。 因为这是前沿理论，所以保证对于每个 $x$，最多有一个 $a$ 使得 $a\rightarrow x$ 成立。

第一行两个数 $n,m$。 之后一行，第 $i$ 个数 $fa_i$ 表示第 $i$ 种 "QwQ" 可以被哪种 "QwQ" 转换得到。 如果 $fa_i$ 为 $-1$ 表示这种 "QwQ" 不可以被任何 "QwQ" 转换得到。 之后一行，第 $i$ 个数 $a_i$ 表示第 $i$ 种 "QwQ" 的个数。

输出一行一个数表示答案。 答案即： 你要求让最少个数的一种 "QwQ" 的个数最多的方案，输出这个方案下最少个数的一种 "QwQ" 的个数。

本题不采用子任务评测，每个测试点 $4$ 分。 | 测试点 | $n$ | $m$ | $a_i$ | 特殊限制 | | :----------- | :----------- | :----------- | :----------- | :----------- | | 1 | $5$ | $5$ | $\leq 5$ | 无 | | 2 | $10$ | $10$ | $\leq 10$ | 无 | | 3 | $1000$ | $1000$ | $\leq 1000$ | A | | 4 | $1000$ | $1000$ | $\leq 1000$ | A | | 5 | $10^5$ | $0$ | 无特殊限制 | A | | 6 | $10^5$ | 无特殊限制 | $0$ | A | | 7 | $10^5$ | 无特殊限制 | 无特殊限制 | A | | 8 | $1000$ | $1000$ | $\leq 1000$ | B | | 9 | $1000$ | $1000$ | $\leq 1000$ | B | | 10 | $10^5$ | $0$ | 无特殊限制 | B | | 11 | $10^5$ | 无特殊限制 | $\leq 1$ | B | | 12 | $10^5$ | 无特殊限制 | 无特殊限制 | B | | 13 | $10^6$ | 无特殊限制 | 无特殊限制 | B | | 14 | $10^5$ | 无特殊限制 | 无特殊限制 | C | | 15 | $10^5$ | 无特殊限制 | 无特殊限制 | C | | 16 | $1000$ | $0$ | $0$ | 无 | | 17 | $1000$ | 无特殊限制 | $0$ | 无 | | 18 | $1000$ | $0$ | 无特殊限制 | 无 | | 19 | $10^5$ | 无特殊限制 | $0$ | 无 | | 20 | $10^5$ | $0$ | 无特殊限制 | 无 | | 21 | $10^5$ | 无特殊限制 | 无特殊限制 | 无 | | 22 | $2\times 10^5$ | 无特殊限制 | 无特殊限制 | 无 | | 23 | $5\times 10^5$ | 无特殊限制 | 无特殊限制 | 无 | | 24 | $8\times 10^5$ | 无特殊限制 | 无特殊限制 | 无 | | 25 | $10^6$ | 无特殊限制 | 无特殊限制 | 无 | 特殊限制 A：$fa_1=1$，对于 $i\geq 1$ 有 $fa_{i+1}=i$。 特殊限制 B：$fa_1=n$，对于 $i\geq 1$ 有 $fa_{i+1}=i$。 特殊限制 C：对于 $i\geq 1$ 有 $fa_i=1$。 对于 $100\%$ 的数据，$1\leq n\leq 10^6,0\leq m,a_i\leq 10^9$。 请不注意常数因子带来的影响。