Bergengóciában, a már megismert Villamoshajtó Bajnokság mellett, nagy hagyományokkal bíró nemzeti sportesemény a Mezei Kincsfelderítő és -begyűjtő Torna. Noha az idei szabálymódosítás értelmében ‐ miszerint a kincsek felkutatásához kémműholdak is igénybe vehetők ‐ a felderítéshez bevetett taktikák alapvetően megváltoztak, a kincsek gyors összegyűjtése továbbra is kihívást jelentő feladat maradt.
Írjunk programot, mely az egyes kincsek elhelyezkedése és értéke, illetve a rendelkezésre álló időkeret alapján meghatározza, hogy milyen útvonalon haladjunk, azaz milyen kincseket és milyen sorrendben érintsünk, hogy a lehető legnagyobb összértékű kincshalmazt gyűjthessük össze. Feltehetjük, hogy egy kincs begyűjtéséhez szükséges idő elhanyagolható; hogy utunkat bármelyik kincstől indíthatjuk; illetve hogy egy időegység alatt egy távolságegységet tudunk megtenni.
A program a mező leírását a standard bemenetről olvassa. Ennek első sora két, szóközzel elválasztott egész számot tartalmaz: a kincsek $1\le N\le 1000$ számát, illetve a rendelkezésre álló $0\le T\le 1000000$ időkeretet. Az ezt követő $N$ sor mindegyike három, szóközzel elválasztott egész számot, az $i$-edik kincs $0\le X_i\mathrm{,}{Y}_i\le 10000$ koordinátáit és $0\le C_i\le 1000$ értékét tartalmazza.
A program a megoldást a standard kimenetre írja. Ennek első sorában az összegyűjtött kincsek $1\le K\le N$ száma szerepeljen, további $K$ db sorában pedig az összegyűjtött kincsek sorszámai a begyűjtés sorrendjében (1-től indexelve).