Time to Study

Time Limit : 1 sec, Memory Limit : 65536 KB

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

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

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

入力

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

1行目 1日の目標時間t(整数)
2行目 勉強の回数 n(整数)
3行目 第1の勉強の開始時刻s 終了時刻f(整数 整数;半角空白区切り)

n+2行目 第nの勉強の開始時刻s 終了時刻f

出力

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

入力例

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/