D. Нанамигийн цахилгаан станц

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нанами тоглоом тоглох дуртай ба үүндээ ч сайн юм. Өнөөдөр тэр цахилгаан станцын үйл ажиллагаагаанд оролцдог шинэ тоглоом тоглож байна. Нанами станцын генераторуудыг хамгийн их үр дүнтэй ажиллахад нь удирдах юм.

Станц $n$ генератортай. Генератор бүрийн үйлдвэрлэх түвшинг тогтоох хэрэгтэй. Үйлдвэрлэх түвшин нь бүхэл тоо (тэг эсвэл сөрөг тоо байж болохгүй) байх ба $i$-р генераторын үйлдвэрлэх түвшин нь $l_{i}$-с $r_{i}$-ийн (хоёулаа орно) хооронд байх ёстой. Генераторын гаралтын түвшин нь $x$ бол тодорхой $f(x)$ квадрат функц ашиглан генераторын гаралтыг тооцоолж чадна. Генератор бүр нь өөрийн функцтэй, $i$-р генераторыг $f_{i}(x)$ функц илэрхийлнэ.

Хэдий тийм ч цаашдаа генераторуудад $m$ хязгаарлалт байна. $i$-р генераторын үйлдвэрлэх түвшин нь $x_{i}$ байг. Хязгаарлалт бүр нь $x_{u} ≤ x_{v} + d$ хэлбэртэй ба $u$ ба $v$ нь хоёр өөр генераторуудын ID-ууд, $d$ нь бүхэл тоо юм.

Нанамигийн тоглоом хэдий төвөгтэй ч түүний итгэл дийлж байлаа. Тэгээд тэр хариултыг нь тооцдог (генераторуудын хамгийн их гаралтын нийлбэр) програм бичихээр шийдэв. Яагаад ч юм энэ чиний ажил болж таарлаа.

Оролт

Эхний мөрөнд $n$, $m (1 ≤ n ≤ 50; 0 ≤ m ≤ 100)$ хоёр бүхэл тоо агуулагдана. Генераторууд ба хязгаарлалтуудын тоо.

Дараа нь $n$ мөр байх ба мөр бүр нь $f_{i}(x)$ функцын коэффициентууд болох $a_{i}$, $b_{i}$, $c_{i} (|a_{i}| ≤ 10; |b_{i}|, |c_{i}| ≤ 1000)$ гурван бүхэл тоог агуулна. $f_{i}(x) = a_{i}x^{2} + b_{i}x + c_{i}$.

Дараа нь дахиад $n$ мөрүүд байх ба мөр бүр нь $l_{i}$, $r_{i} ( - 100 ≤ l_{i} ≤ r_{i} ≤ 100)$ хоёр бүхэл тоог агуулна.

Дараа нь $m$ мөрүүд байна. Мөр бүр хязгаарлалтыг тодорхойлох $u_{i}$, $v_{i}$, $d_{i} (1 ≤ u_{i}, v_{i} ≤ n; u_{i} ≠ v_{i}; |d_{i}| ≤ 200)$ гурван бүхэл тоо агуулна. $i$-р хязгаарлалт нь $x_{u_{i}} ≤ x_{v_{i}} + d_{i}$.

Гаралт

Бүх генераторуудын хамгийн их гаралт болох нэг бүхэл тоо хэвлэнэ. Энэ нь дор хаяж нэг зөв тохиргоо байна гэсэн баталгаа юм.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3 3
0 1 0
0 1 1
0 1 2
0 3
1 2
-100 100
1 2 0
2 3 0
3 1 0
Гаралт
9
Оролт
5 8
1 -8 20
2 -4 0
-1 10 -10
0 1 0
0 -1 1
1 9
1 4
0 10
3 11
7 9
2 1 3
1 2 3
2 3 3
3 2 3
3 4 3
4 3 3
4 5 3
5 4 3
Гаралт
46

Тэмдэглэл

Эхний жишээний, $f_{1}(x) = x$, $f_{2}(x) = x + 1$, $f_{3}(x) = x + 2$, тэгэхээр үйлдвэрлэх түвшингийн хамгийн их нийлбэр байна. Хязгаарлалтууд $x_{1} ≤ x_{2}$, $x_{2} ≤ x_{3}. Оновчтой тохиргоо нь $x_{1} = x_{2} = x_{3} = 2$, тиймээс үр дүн нь 9 байна.

Хоёр дахь жишээний хувьд хязгаарлалтууд нь $|x_{i} - x_{i + 1}| ≤ 3$, $1 ≤ i < n$ байна. Оновчтой тохиргооны нэг нь $x_{1} = 1$, $x_{2} = 4$, $x_{3} = 5$, $x_{4} = 8$ ба $x_{5} = 7$ байна.

Сэтгэгдлүүдийг ачааллаж байна...