演習課題「習課題「スケジューラー問題」」

スケジュールに空きがあるかどうか調べ、重複が無ければ予定を埋める、スケジューラーを作成する問題です。

n マスの、ある月のカレンダーが与えられます。
カレンダーには 1 から 31 日までの日付が書かれています。
今回、曜日は特に考える必要はありません。

予定は m 個与えられます。各予定は a_i 日から始まり、1日以上の期間 b_i 日間が決められています。
(3日からはじまり、7日間の予定、と言うイメージです。)
それぞれの予定は優先度順に並んでいるので、順番にカレンダーのマスに埋めていきます。

予定は必ず与えられた期間分( b_i 日間)確保しなくてはならず、優先度が高い予定と
重なってしまった場合はその予定を断る事にします。
また、カレンダーのマスを超えてしまうような予定も断る事にします。



全ての予定がカレンダーのマスに割り当て終わった時に、予定が埋まっているカレンダーの
マスの総数を出力するプログラムを作成して下さい。

■入力例
31 8 …31日の月、8つの予定
1 15 …第1優先の予定:1日からはじまり、15日間の予定
2 13 …第2優先の予定:2日からはじまり、13日間の予定
.
.
21 8 …第8優先の予定:21日からはじまり、8日間の予定

※paizaに会員登録すると無料で動画学習コンテンツをご利用いただけます
会員登録する

#11:集計処理

このチャプターでは、最終的に着席できた人数を集計します

長テーブルのうなぎ屋


Img 04 03 下記の問題をプログラミングしてください。

東京の下町に長テーブルで有名な老舗うなぎ屋がありました。

そのうなぎ屋にはとても大きい長テーブルがあり、テーブルの周りにn個の座席が配置されています。
座席には、時計回りに1, 2, …, nと番号が振られています。
座席はテーブルの周りに配置されているので、座席番号nの座席と1の座席は隣接しています。(下記図を参照の事)



今、m個のグループの人達が座席に順番に座りに来ます。i番目(1≦i≦m)のグループの人数をa_i人とします。
彼らは、長テーブルに並んだ座席の内、ある連続するa_i個の座席に一斉に座ろうとします。

ただしお客さんは江戸っ子なので、それら座席のうち、いずれか一つでも既に先客に座られている座席があった場合、
一人も座らずにグループ全員で怒って帰ってしまいます。江戸っ子は気が早いんでぃ。

入力では、i番目のグループが座ろうとする連続した座席の位置は、整数b_iにより指定されます。
i番目のグループは、座席番号b_iの座席を始点として、そこから時計回りにa_i個分の座席に座ろうとします。

最後のグループが座りに来た後、無事に長テーブルの座席に着席出来ている人数を出力するプログラムを作成してください。


入力される値

入力はm+1行から成ります。
1行目にはn(座席数)とm(グループ数)が半角スペース区切りで入力されます。
i+1行目(1≦i≦m)には2個の整数a_i(グループの人数)とb_i(着席開始座席番号)が半角スペース区切りで入力されます。

入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。


期待する出力

最後のグループが座りに来た後、無事に座席に着席出来ている人数を1行で出力してください。


条件

すべてのテストケースにおいて、入力される値は以下の条件を満たします。

1 ≦ n ≦ 100
1 ≦ m ≦ 100
1 ≦ a_i ≦ n
1 ≦ b_i ≦ n

入力例1

6 3
3 2
1 6
2 5

出力例1

4

入力例2

12 6
4 6
4 8
4 10
4 12
4 2
4 4

出力例2

12