No.568 じゃんじゃん 落とす 委員会

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 35
作問者 : WA_TLEWA_TLE / テスター : square1001square1001
0 ProblemId : 1738 / 出題時の順位表

問題文

JOI(JanJan Otosu Iinkai)は、何らかの合宿の選考をしているようだ。

この大会では、解き終えたときの時間や、WA数を一切考慮しないので、単純に完答数が重要になる。

いま、本選に出す問題のうち3問は確定したが、AとBの2問だけ決まってない。

2問の難易度はそれぞれ独立に,0以上100001以下の整数に決めれる。

JOIが行う本選にn人の参加者がいる。(1<=n<=100000)

合宿の予算がないので、委員会は残った2問の難易度をうまく調整して

2完以上を達成した人数をm人以上にしつつ、3完以上を最小化したい。(1<=m<=n)

各人の能力から、(Xi,Ai,Bi)が与えられる。(0<=Xi<=3,0<=Ai , Bi<=100000)

Xiは、すでに決まった問題のうち完答できる数である。

Aiは、全体的なA問題の難易度をSAとしたとき、Ai>=SAなら完答できる、という意味である。

Biは、全体的なB問題の難易度をSBとしたとき、Bi>=SBなら完答できる、という意味である。

その時の、3完以上の人数を出力せよ。

※この問題はフィクションです。実在する組織、人物名には一切関係ありません。

入力

N M
xi ai bi 

出力

最後に改行してください。

サンプル

サンプル1
入力
10 5
1 2 5
2 4 6
2 3 5
0 1 3
3 2 2
0 1 4
0 5 1
1 2 1
0 6 7
1 4 4
出力
2

例えば、Aの難易度=4 Bの難易度=7とすると良いです。

サンプル2
入力
34 24
2 11 10
0 0 9
1 0 3
0 4 9
3 5 4
1 10 5
1 5 3
0 2 6
2 6 8
0 9 8
3 3 6
0 1 11
1 4 6
0 2 2
0 6 11
2 10 10
3 7 11
3 11 6
3 0 0
2 3 10
0 2 2
2 8 7
0 3 11
3 11 9
0 1 0
0 9 7
1 9 5
1 8 5
2 9 1
0 10 9
2 6 6
0 6 6
2 1 5
2 6 1
出力
14

例えば,Aの難易度=2,Bの難易度=9とすると、 24人が2完以上をして、3完以上が14人になります。

つまり、2完は合宿にいけないということです。かなしいね。(余談)

サンプル3
入力
5 2
3 1 3
2 1 4
3 4 2
1 2 3
3 4 6
出力
3

はい。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。