3278. 最后的时光2

【题目背景】

【题目描述】

Knight想起有那么一次，他和MANDAWIUDFAWJNAIFN等人一起玩CS....

目前Knight想回忆起这些东西，毕竟不正向的记忆也是一段记忆....

在开始的时候，Knight可以利用现有的m个金币来购买枪支装备来获得战

力，而且由于开挂，他可以得到别人在每局中的战力，每一局的刷新都可以让

Knight重置为m个金币，在F局下，Knight如何购买枪支防具，以使他每次都能胜利？

注意：

在本题中，Knight只需面对一个对手，但是Knight初始战力永远为0，这意味着Knight如果

什么都不买，直接输掉；

任何种类装备只允许购买一次（在Fi局状态下）；

Knight在每局的开始可以购买任意多的装备来最大限度提升自己的战力

判定胜利的条件：Knight战力严格大于对方战力（由于相同战力下，Knight技术不占优势）

【输入格式】

两个正整数F,m,表示游戏局数和每局更新他可以获得的金币

接下来有F行，每行对应从1-->Fi代表敌方的战力值

一个正整数n，表示商店可购买的枪支装备种类

接下来有n行，每行有一个正整数ni,nj，表示每种装备的装备花费和可提升的战力值

【输出格式】

若存在局局获胜的可能，则输出"Knight win"

反之，则输出获胜次数（全盘皆输，照样输出）

【样例输入】

1 400



200



1



400 210

【样例输出】

Knight win

【提示】

购买唯一一个枪支，钱刚好花完，而且当前战力可以击败对手

【数据规模】