Amazing Race
Пролетен Турнир по Информатика, 2010
Time Limit: 0.2s, Memory Limit: 64MiB
"The Amazing Race" е отборно състезание, в което участниците обикалят света преминавайки през различни изпитания и изпълнявайки различни задачи. Първият отбор, който изпълни всичките си задачи и стигне до финала, побеждава.

Ели и нейните съученици организират нещо подобно в училище. Форматът в случая е по-локален – вместо по света, задачите са локирани в София – но останалите правила са подобни. Отборите са от по трима ученици, като задачите са, например, да си направят снимка с петима непознати, да се качат на върха на НДК, да снимат някоя от табелите за околовръстния път, да си купят продукт от три различни вериги заведения за бързо хранене и много други.

Задачите изискват определено време за да бъдат изпълнени. Например, докато това да се качат на върха на НДК не е толкова трудно, да намерят петима непознати, които биха желали да се снимат с тях, би могло да отнеме повече време. За такива неща Ели е незаменима =).

Всеки от отборите трябва да изпълни определен брой задачи, след което да стигне до финала. За да спечелят играта всички се стремят да свършат възможно най-бързо. Началното място на отборите, позициите на задачите, както и на финала, могат да бъдат зададени на картата чрез координатите им (X, Y). За да стигнат от точка (X1, Y1) до точка (X2, Y2) на участниците им е нужно време |X1X2| + |Y1Y2| (Манхатъново разстояние между точките). Допълнително, за всяка задача ще бъде дадено и времето, нужно за нейното изпълнение. Отборите могат да изпълняват една задача повече от веднъж, но не последователно (примерно не могат два пъти поред да се качат на НДК, но могат да се качат на НДК, да се снимат с петима непознати и после пак да се качат на НДК).

Помогнете на Ели като намерите най-краткото време, за което всеки от отборите може да изпълни определен брой задачи и да стигне до финала.
Вход
На първия ред на стандартния вход ще бъде зададени числата T и K – съответно броят отбори и колко задачи трябва да изпълни всеки от тях. На следващите Т реда ще има по две цели числа Xi и Yi – началните координати на i-тия отбор. На следващия ред ще бъде зададено числото N – броят задачи, които отборите биха могли да изпълнят. На следващите N реда ще бъдат зададени по три цели числа – Xi, Yi, Pi – съответно позицията на i-тата задача и времето й за изпълнение. На последния ред на стандартния вход ще бъдат зададени числата FX и FY – координатите на финала.
Изход
На стандартния изход изпечатайте T реда съдържащи по едно цяло число – минималното време за завършването на състезанието за всеки от отборите. i-тият ред ще съответства на времето на i-тия отбор от входа.
Ограничения
  • 1 ≤ K ≤ 10
  • 1 ≤ T, N ≤ 500
  • 0 ≤ Xi, Yi, Pi ≤ 10,000
  • Всички координати във входа ще са различни.
Примерен Вход Примерен Изход
4 3 8 6 1 9 9 1 3 5 5 4 6 3 6 5 2 7 4 2 9 2 1 7 2 4 8 3 15 20 13 16
В надпреварата участват 4 отбора, всеки от който трябва да изпълни по 3 задачи. Началните позиции на отборите са (8, 6), (1, 9), (9, 1) и (3, 5). Състезателите имат избор между 5 задачи, които изискват по 3, 2, 2, 1 и 4 минути, съответно. Финалът се намира в (8, 3).
Оптималните стратегии за отборите са: задачи (3, 2, 3) за отбор 1; (1, 2, 3) за отбор 2; (4, 5, 4) за отбор 3; и (2, 3, 4) за отбор 4.
Мрън!