パケットモンスターというゲームがあります。モンスターを捕まえ、育て、戦わせたり交換したりするゲームで、日本中で大流行しています。もちろん、わたしのクラスでも。だからわたしもこのゲームでみんなと遊べるようにモンスターを育てているけど、悲しいことに対戦する相手がいません。わたしは積極的に人に話しかけるのが得意なタイプではないからです。だから今日も、クラスメイトが誘ってくれるのを待ちながら、独り寂しくモンスターのレベルを上げています。
そしてついに、待ち望んでいた瞬間が訪れました。クラスメイトの一人が対戦しないかとわたしに話を持ちかけてきたのでした。彼女は自慢気に、彼女のモンスターたちを見せてくれました。
一般的なパケットモンスターの対戦ルールでは、各プレイヤーがそれぞれN 匹のモンスターを用意し、互いに1 匹ずつ戦わせます。各モンスターには成長の度合いを示す「レベル」という数値があり、レベルが大きいモンスターが必ず勝ちます。同レベルのときは引き分けです。一度戦ったモンスターは、それ以上戦わせることができません。こうして一対一の戦いをN 回行ったあと、過半数の勝利を収めたプレイヤーが勝者となります。
わたしは、彼女のモンスターを見た瞬間、嫌な予感がしました。彼女のモンスターはどれも、とても強そうなのです。わたしと戦ってくれるのなら負けてもかまいません。でも、あまりにもひどい負け方をしたら、"こいつと戦っても面白くないな"とか思われて、もう遊んでくれなくなるんじゃないかな。それは、とても嫌です。だから、
「ごめん、わたしまだモンスターをN 匹持ってなくて」
嘘をつきました。
N 回勝負では勝ち目がなくても、それより少ない数のモンスターで勝負する特別ルールなら、もしかしたら勝てるかもしれません。さっきは負けたってかまわないと言ったけど、やっぱり勝てたら嬉しいです。
彼女はこの特別ルールを受け入れてくれました。つまり、二人が持っているモンスターからお互いに k 匹選んで一匹ずつ順番に戦わせ、過半数の(つまり、k/2 より大きな数の) 勝利を収めた方が勝ちとなります。
さっきわたしは、彼女のモンスターのレベルを知ってしまいました。彼女がどのモンスターを選び、どんな順番で出してくるのかはわかりません。でも、対戦させるモンスターの数kをわたしがうまく決めれば、彼女がどんな選択をしようとわたしが勝つことができるかもしれません。
皆さんにお願いです。モンスターの数 N と、二人が持っているモンスターのレベルを入力すると、彼女がどんな選択をしようとわたしが勝てるような最小のモンスターの数 k を出力するプログラムを作成して下さい。
入力は複数のデータセットからなる。入力の終わりはゼロ１つの行で示される。各データセットは以下の形式で与えられる。
N a1 a2 ... aN b1 b2 ... bN
１行目にモンスターの数 N (1 ≤ N ≤ 40000) が与えられる。２行目に自分のモンスターのレベル ai (1 ≤ ai ≤ 100000) が１つの空白区切りで与えられる。３行目にクラスメイトのモンスターのレベル bi (1 ≤ bi ≤ 100000) が１つの空白区切りで与えられる。
データセットの数は 50 を超えない。
データセットごとに、k (1 ≤ k < N) が存在すれば最小値を１行に出力する。もし、k が存在しないか、k が N に等しければ NA と出力する。
10 4 9 1 9 5 9 2 3 2 1 8 7 6 5 10 5 5 4 7 6 5 4 3 2 5 1 4 4 4 4 4 4 4 1 3 2 4 3 2 1 0
3 1 NA
１つ目のデータセットでは、わたしは３匹での対戦を提案し、レベルが [9, 9, 9] のモンスターを選べば良い。相手のレベル 10 以外のどのモンスターにも勝てるので、少なくとも２勝できる。２匹での対戦では １勝１敗になる可能性があり、これは過半数の勝利とは言えないので、2 は答えにならない。
２つ目のデータセットでは、わたしは最強のモンスターを１匹選べば良い。
３つ目のデータセットでは、わたしがどの k 匹を選び、どの順番で出したとしても、彼女が全く同じモンスターを同じ順番で出してきて引き分けになる可能性がある。したがって、「彼女がどんな選択をしようとわたしが勝つことができる」とは言い切れない。