Time to Study

Time Limit : 1 sec, Memory Limit : 65536 KB

勉強を開始した時刻と終了した時刻の情報を基に、1日で勉強した時間の合計が t 以上であるかをチェックし、達していない場合は足りない時間を求めるプログラムを作成します。時間は1時間を1単位とし、分や秒は考えないものとします。時刻は24時間表記で1時間単位で表します。

1日の勉強の目標時間と、実際に勉強した時間の情報(勉強の回数 n、それぞれの勉強の開始時刻 s と終了時刻 f)を入力とし、勉強時間の合計が目標に達しているかを調べ、達していれば "OK" を、達していない場合は足りない時間を出力するプログラムを作成してください。ただし、それぞれ行った勉強時間は重複しません。

例:
目標時間 勉強した時間 判定
10時間 6時〜11時 = 5時間
12時〜15時 = 3時間
18時〜22時 = 4時間
OK
14時間 6時〜11時 = 5時間
13時〜20時 = 7時間
2時間不足

入力

複数のデータセットの並びが与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下の形式で与えられます。

t
n
s1 f1
s2 f2
:
sn fn

1行目に1日の目標時間 t (0 ≤ t ≤ 22)、 2行目に勉強の回数 n (1 ≤ n ≤ 10)が与えられます。続く n 行に i 回目の勉強の開始時刻 si と終了時刻 f (6 ≤ si, fi ≤ 22) が与えられます。

データセットの数は 100 を超えません。

出力

データセットごとに、OK または足りない時間を1行に出力します。

入力例

10
3
6 11
12 15
18 22
14
2
6 11
13 20
0

出力例

OK
2

Source: PC Koshien 2011, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2011
(revised version)
http://www.pref.fukushima.jp/pc-concours/