{"trustable":true,"sections":[{"title":"説明","value":{"format":"MD","content":"大学の期間中、教室を借りる必要がよくあります。学部がイベントを開催する大きなものから、学習グループの自習討論のような小さなものまで、学校に教室を借りる申請をする必要があります。教室の大きさや機能は異なり、借りる人の身分も異なるため、教室を借りる手続きも異なります。\n\n大量の教室の貸出情報に直面して、プログラミングでこの問題を解決したいと考えています。\n\n私たちは次の $n$ 日間の教室の貸出情報を処理する必要があります。その中で、$i$ 日目には学校に $r_i$ 室の教室が借りられます。合計 $m$ 件の注文があり、それぞれの注文は3つの正の整数で表され、$d_j,s_j,t_j$ は特定の借り手が $s_j$ 日目から $t_j$ 日目まで教室を借りる必要があることを示しています($s_j$ 日目と $t_j$ 日目を含む)、毎日 $d_j$ 室の教室を借りる必要があります。\n\n私たちは、借り手が教室の大きさや場所に要求を持たないと仮定します。つまり、各注文に対して、毎日 $d_j$ 室の教室を提供する必要がありますが、それらが具体的にどの教室であるか、毎日同じ教室であるかは考慮しません。\n\n教室の貸出の原則は先着順であり、つまり、私たちは注文の順序に従って教室を割り当てる必要があります。割り当ての過程で、ある注文が完全に満たされない場合、教室の割り当てを停止し、現在の申請者に注文の修正を通知する必要があります。ここで、満たされないとは、$s_j$ 日目から $t_j$ 日目の間に、少なくとも1日、残りの教室の数が $d_j$ 室未満であることを指します。\n\n今、私たちは、すべての注文が完全に満たされるかどうかを知る必要があります。もしそうでない場合、どの申請者に注文の修正を通知する必要があるかを知る必要があります。"}},{"title":"入力","value":{"format":"MD","content":"最初の行には2つの正の整数 $n,m$ が含まれ、日数と注文の数を示します。\n\n2行目には $n$ 個の正の整数が含まれ、その中の第 $i$ 個は $r_i$ であり、$i$ 日目に借りられる教室の数を示します。\n\n次に $m$ 行があり、それぞれの行には3つの正の整数 $d_j,s_j,t_j$ が含まれ、借りる数量、借り始める日、借り終わる日がそれぞれ示されています。\n\n各行の隣接する2つの数の間には1つの空白が挿入されています。日数と注文はすべて $1$ から始まる整数で番号付けされています。"}},{"title":"出力","value":{"format":"MD","content":"すべての注文が満たされる場合、1行だけを出力し、整数 $0$ を含めます。そうでない場合(注文が完全に満たされない場合)\n\n2行を出力します。最初の行には負の整数 $-1$ を出力し、2行目には注文を修正する必要がある申請者の番号を出力します。"}},{"title":"サンプル 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3 \n2 5 4 3 \n2 1 3 \n3 2 4 \n4 2 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1 \n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"ヒント","value":{"format":"MD","content":"【入力出力サンプルの説明】\n\n第 $1 $ 件の注文が満たされた後、$4 $ 日目の残りの教室数はそれぞれ $0,3,2,3$ です。第 $2$ 件の注文は第 $2 $ 日目から第 $4$ 日目まで毎日 $ 3 $ 室の教室を提供することを要求していますが、第 $3$ 日目の残りの教室数は $ 2$ であるため、満たすことができません。割り当てが停止され、第 $2$ 件の申請者に注文の修正を通知します。\n\n【データ範囲】\n\n10% のデータに対しては $1≤ n,m≤ 10$;\n\n30% のデータに対しては $1≤ n,m≤1000$;\n\n70% のデータに対しては $1 ≤ n,m ≤ 10^5$;\n\n100% のデータに対しては $1 ≤ n,m ≤ 10^6,0 ≤ r_i,d_j≤ 10^9,1 ≤ s_j≤ t_j≤ n$。\n\n\nNOIP 2012 強化グループ 第2日 第2問\n\n2022.2.20 新しいハックデータセットを追加"}}]}