#L9740. 洛谷模拟「KDOI-06-J」ION 比赛

洛谷模拟「KDOI-06-J」ION 比赛

「KDOI-06-J」ION 比赛

题目描述

在 ION 比赛中,总共有 nn 道题目。每道题目的满分均为 100100 分。

ii 道题有 aia_i 个测试点,且该题的所有测试点分值相等,因此 aia_i 一定是 100100 的因数。每通过一个测试点,你将会得到与该测试点分值相等的分数。

通过一些技术手段,你了解到 ION 比赛今年的 Au 分数线是 tt 分。

现在,你在第 ii 道题中已经通过了 bib_i 个测试点。作为一名策略选手,你想知道:对于任意 1jn1\le j\le n,如果你在比赛剩下的时间内死磕第 jj 题(不做其他题目),需要至少再多通过几个测试点以获得 Au,也就是说,使你的总分 t\ge t

当然,你有可能无法通过死磕某一道题目翻盘(获得 Au),此时你需要输出 NaN

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 nn,表示题目总数。

接下来 nn 行,一行两个非负整数 ai,bia_i,b_i,表示第 ii 题的测试点个数和你已经通过的测试点个数。保证 aia_i100100 的因数且 biaib_i\le a_i

最后一行一个整数 tt,表示 Au 分数线。

输出格式

输出到标准输出。

如果你的分数已经达到 Au 线,请输出一行一个字符串 Already Au.

否则,输出 nn 行。在第 ii 行中你应该输出以下两种格式之一:

  • 一个正整数 cic_i,表示在第 ii 道题目中你需要至少再通过多少个测试点才可以获得 Au。
  • 一个字符串 NaN,表示你无法通过这题翻盘(获得 Au)。

样例 #1

样例输入 #1

7
100 100
20 20
25 23
25 10
20 14
25 11
20 0
447

样例输出 #1

NaN
NaN
1
1
1
1
1

样例 #2

样例输入 #2

7
100 100
20 20
25 23
25 10
20 14
25 11
20 0
446

样例输出 #2

Already Au.

样例 #3

样例输入 #3

7
100 100
20 20
20 10
25 13
20 20
25 16
20 6
509

样例输出 #3

NaN
NaN
3
4
NaN
4
3

样例 #4

样例输入 #4

7
100 100
20 19
20 20
25 11
20 20
25 25
20 6
509

样例输出 #4

Already Au.

提示

【样例解释 #1】

容易发现目前的分数是 100+100+92+40+70+44=446100+100+92+40+70+44=446,而分数线为 447447,故在任何一道没有拿到满分的题中多通过一个测试点即可。

【数据范围】

对于所有数据保证:1n71\leq n\leq 70biai0\leq b_i\leq a_i1ai1001\leq a_i\leq 100aia_i100100 的因数,0t100n0\leq t\leq 100n

测试点编号 nn aia_i 特殊性质
11 7\leq7 100\leq100 保证目前分数大于等于 tt
232\sim3 =1=1
454\sim5 7\leq7 =100=100
6106\sim10 100\leq100