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

問題

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


ベルトコンベアがある。そこに左から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行目にめうめうの幸福度の最小値を、２行目に最大値を出力する。
• 改行を忘れないこと。

制約

• 1≦N≦10¹², 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：タコヤキオイシクナールめう」