0465 - ベルトコンベアちくわ大食い大会

時間制限 2 秒 / メモリ制限 256 MB / 得点 15 / Writer ei1409 / x 2 / 統計 /


誤差
1e-6
TLE
2sec
MLE
256MB
得点
15

問題

芽兎めう「ベルトコンベアちくわ大食い大会めう!!!!!!」
霜月凛「はんこ屋、無謀よ、やめなさい」
山形まり花「大丈夫だよ!絶対、大丈夫だよ!!」


ベルトコンベアがある。そこに左からN個のちくわをのせる。ちくわは何かの力によってその場から動くことはない。
芽兎めう(めうめう)は、このベルトコンベアを左から右へ移動する。移動する際にちくわを全て食べる。


大食い大会といっても、これは少し特殊である。
ちくわiには、「幸福度」なるものが存在する。幸福度はあるパラメータ(a, b)によって定められている。
幸福度rのめうめうが幸福度パラメータ(a, b)のちくわを食べた際のめうめうの「幸福度」は、

『r × a + b』

となる。

この大会は、1~Nまでの全てのちくわを食べ終えた際の「幸福度」が最も高い者が優勝するシステムである。
そして、ちくわiは時間をランダムにおいてM回にわたり別の幸福度パラメータを持ったちくわに置き換えられる。

例として、ちくわ2つに(2, 1), (-1, 3)という幸福度パラメータがあるものを取り上げる。 このような流れで大会は行われる。

和泉一舞「何か落ちてるわ・・・ 何これ、ちくわの入れ替え表?」
颯爽とイブの元に現れた凛「でかしたわ洋服屋。これではんこ屋を救うわよ」

あなたは凛から「ちくわの入れ替え表」を受け取った。
これには、ちくわの入れ替えのタイミングと場所、そのちくわの幸福度パラメータが記されていた。

最初の段階では、ちくわの幸福度パラメータは全て(1, 0)で、めうめうの幸福度は1である。
つまり、最初の段階でベルトコンベアをめうめうが滑れば、最終的な幸福度は1のままである。

この表を元に、あなたは凛にめうめうの幸福度の最大値を教えて、めうめうを救ってあげよう。
凛「あ、後ついでに最小値も出して頂戴。 ・・・理由?なんとなくよ」

入力

N M
p1 a1 b1
・   ・   ・
・   ・   ・
・   ・   ・
pM aM bM
  • 1行目にちくわの個数N、ちくわの交換回数Mが与えられる。
  • 2~M-1行目に交換するちくわの情報(場所p, パラメータa, パラメータb)が与えられる。

出力

min
max
  • 1行目にめうめうの幸福度の最小値を、2行目に最大値を出力する。
  • 改行を忘れないこと。

制約

  • 1≦N≦1012, 0≦M≦100000
  • 1≦r≦N, 0≦a, b≦1 (実数を含む)
  • 許容誤差は10-6である。

入力例

入力例1

1 1
1 1 0

出力例1

1
1

解説

  • 1度ちくわが入れ替えられているが、入れ替え前後でちくわの幸福度パラメータに変化はない。よって幸福度は1である。

入力例2

3 2
2 -1 1
2 1 0.5

出力例2

0
1.5

解説

  • 1回目の入れ替え後は、2個目のちくわで「1 x (-1) + 1 = 0」
  • 2回目の入れ替え後は、2個目のちくわで「1 × 1 + 0.5 = 1.5」
  • よって、最小値0, 最大値1.5となるので、「1.5」と出力する。

入力例3

4 5
1 -0.8 0.5
2 0.72 -0.21
3 1 0.8
4 0.3 0.4142
3 1 0.8

出力例3

-0.426
1

入力例4

10 10
6 0.5674 -1
3 -0.432 0.1235
8 0.92 0
4 -0.673 0.12578
6 0.986 -0.567
1 0.11111 1
10 0.98765 -0.1234
10 0.18543 -0.16532
9 -0.756 0.54849
2 -1 0.74436

出力例4

-1.175043
1

りんりんせんせーたちからのアドバイス

凛「coutの実数精度指定に『cout.precision(整数);』があるわ。
    これでprintfを使わなくても実数の精度を気にしなくて済むわね。」
めう「元ネタはARC008-D:タコヤキオイシクナールめう」