Deathstars
TopCoder SRM 543
Time Limit: 0.1s, Memory Limit: 64MiB
Принцеса Ели наскоро попадна на секретни планове за строежа на цяло ято звезди на смъртта. Сега тя и бунтовниците всячески се опитват да ги унищожат преди да са напълно завършени.

Бунтовниците имат няколко кораба, за които се знае началната и крайната точка в която ще бъдат телепортирани и ще изчезнат, тяхната скорост, обхват, и енергия. Корабите могат да почнат да стрелят по звездите на смъртта в момента, в който се телепортират на бойното поле до момента, в който изчезнат. Кораб може да стреля по звезда ако:

  • Целта е достатъчно близо (попада в неговия обхват)
  • Корабът все още има енергия за лазерите си

За нещастие, част от защитата на звездите на смъртта вече е активна и пречи на повече от един кораб да я атакува едновременно. Тоест, корабите трябва да спазват и още едно правило:

  • Във всеки момент всяка звезда е атакувана от най-много един кораб

Това, разбира се, не пречи на всеки от корабите да атакува по няколко цели едновременно. Стрелянето по една звезда на смъртта отнема по единица енергия за секунда. Стреляне по T звезди едновременно отнема T единици енергия на секунда. Възможно е стрелянето по звезда за периоди, по-кратки от секунда (дробни периоди).

Ели ви е дала координатите на звездите на смъртта и възможностите на всеки от корабите. За простота ще представим битката в 2D пространството, като всеки кораб и звезда са представени чрез точки (разстоянията в космоса са толкова големи!). Траекторията на корабите е сегмент в пространството (между началната и крайната точка). Сега момичето се чуди какво е максималното количество енергия, което може да се употреби в стреляне по звездите, ако корабите атакуват оптимално.
Вход
На първия ред на стандартния вход ще бъдат зададени двете цели числа N и M – съответно броя звезди на смъртта и броя кораби. На следващите N реда ще бъдат здадени по две цели числа Xi Yi, указващи координатите на звездите. На следващите M реда ще има по седем цели числа SXi SYi EXi EYi Si Ri Ei, където (SXi, SYi) и (EXi, EYi) задават съответно началната и крайната точка на i-тия кораб, Si е неговата скорост, Ri е неговият обхват, а Ei е неговата налична енергия.
Изход
На стандартния изход изведете едно число с плаваща запетая – максималното количество енергия, което може да бъде изстреляно по звездите на смъртта, ако корабите атакуват оптимално. Отговорът ще бъде зачетен за верен при абсолютна или релативна разлика, по-малка от 10-9.
Ограничения
  • 1 ≤ N, M ≤ 20
  • 1 ≤ Xi, Yi, SXi, SYi, EXi, EYi, Si, Ri, Ei ≤ 1,000
Примерен Вход Примерен Изход
2 4 12 10 7 5 10 10 12 10 1 1 3 6 1 8 10 1 2 3 3 6 8 2 5 3 1 42 42 42 42 6 6 6 4.983770744659944
13 11 141 393 834 847 568 43 18 228 515 794 167 283 849 333 719 738 434 261 613 800 127 340 466 938 598 601 410 951 472 100 337 226 210 713 352 677 908 731 687 300 191 41 337 92 446 716 213 598 889 446 907 148 650 203 168 556 470 924 344 369 198 300 182 350 936 737 533 45 410 871 488 703 746 631 80 270 777 636 539 172 103 56 466 906 522 98 693 77 309 768 698 846 110 14 643 14 755 724 664 465 263 759 120 31.965770956316362
В първия пример има две звезди на смъртта и четири кораба. Въпреки, че първият кораб има останала енергия, той изчезва преди да я е изразходвал напълно. Последният кораб пък се появява и изчезва мигновено.
Мрън!