SPOJ in Armenian

Ք.ա. 80 թվականն  էր. Տիգրան Մեծի տերությունը ձգվում էր Սև ծովից  Պարսից ծոց, Միջերկրական ծովից Կասպից ծով, զբաղեցնելով գրեթե 3 մլն քառ. կմ տարածք: Տիգրանի այսպիսի նվաճումներից հետո Արտաշատն այլևս չի կարող մայրաքաղաք մնալ, քանզի տեղակայված է տերության ծայր հյուսիսում, իսկ Անտիոքը տեղակայված է բուն հայկական տարածքներից  դուրս և գերազանցապես ունի օտար բնակչություն: Հետևապես հիմա Տիգրան մեծի գլխավոր խնդիրը նոր մայրաքաղաքի կառուցումն է: Տիգրանն Մեծն ունի բնակավայրերի ցուցակ, որոնք կարող են մայրաքաղաք դառնալ, օգնիր նրան պարզելու, թե, որ բնակավայրն է մայրաքաղաք դարձնելը ամենանպատակահարմարը: Ձեր գործն ամենևին էլ հեշտ չէ,քանի որ մայրաքաղաք դառնալու համար բնակավայրը պետք է բավարարի հետևյալ պահանջներին.

·  չլինի նավահանգիստ (բոլոր նավագիստների զույգերի միջև գոյություն ունի գոնե մեկ ծովային ճանապարհ: Երաշխավորվում է, որ նավահանգիստների թիվը >=2),

·  չլինի ամրոց (ամրոցներից ոչ մի ճանապարահ դուրս չի գալիս, դրանք կառուցվում են պաշտպանական նպատակներով, բացի ամրոցներից մնացած բոլոր բնակավայրերը կապակցված են),

·  բավականաչափ հեռու լինի հակառակորդի ճամբարներից,

·  ընկած լինի բուն հայկական տարածքներում (Մեծ Հայք, Կոմմագենե (լատինատառ Mec-Hayq, Kommagene) Փոքր Հայքն այդ տարիներին ցավոք Տիգրան Մեծի տերության տարածքում չի եղել, հետևապես թեսթերում բնակավայրեր, որոնք գտնվել են Փոքր Հայքում չեն լինի),

·  ցուցակում առկա տերության  բոլոր կարևորագույն բնակավայրերը տվյալ բնակավայրին միացնող մինիմալ ճանապարհների գումարը լինի մինիմալ:

Եթե մեկից ավելի բնակավայրեր բավարարում են տրված բոլոր պահանջներին պետք է արտածել ամենաշատ բնակչություն ունեցող բնակավայրի համարը ցուցակում: Երաշխավորվում է, որ այն բոլոր բնակավայրերը, որոնք միաժամանակ բավարարում են բոլոր պայմաններին ունեն տարբեր թվով բանակիչներ: Երաշխավորվում է, որ Արտաշատը բավարարում է առաջին չորս պայմաններին և քաղաքի բնակչությունը 60 հազար է: Հնարավոր են դեպքեր, երբ տրված բնակավայրերից  ոչ մեկը չի բավարարում վերևում նշված պայմաններին, այդ դեպքերում պետք է տպել ”Artashatn e aynuamenayniv lavaguyn tarberaky”  արտահայտությունը, առանց չակերտների:

Մուտքային տվյալներ

Մուտքի առաջին տողում տրված են N (0 <= N <= 100) մայրաքաղաք դառնալու համար առաջադրված բնակավայրերի քանակը, M(0<=M<=500) ցուցակի բնակավայրերը իրար կապող ճանապարհների քանակը, K(0<=K<=100) հակառակորդի ճամբարների քանակը և d(1<=d<=1000) մինիմալ հեռավորությունը, որ մայրաքաղաքը պետք է ունենա հակառակորդի ճամբարներից: Հաջորդ տողում տրված են N թվեր, որոնցից i-երորդը ցույց է տալիս թե ինչ երկարություն ունի Արտաշատը այդ բնակավայրին միացնող ճանապարհը, կամ -1, եթե այդպիսի ճանապարհ չկա (եթե Արտաշատը այդ բնակավայրին կապող ճանապարհ չկա, պարտադիր չէ, որ բնավայրը ամրոց լինի):

Հաջորդ N տողերից յուրաքանչյուրում տրված է քաղաքի նկարագիրը 4 պարամետրով: Առաջին պարամետրը ցույց է տալիս, թե քաղաքը որտեղ է գտնվում, բոլոր տեղանունները ժամանակին գոյություն ունեցած Տիգրան Մեծի տերության իրական հատվածներ են (Mec-Hayq, Kommagene, Asoriq, Kapadovkia, Kilikia, Osroene, Migdonia, Adiabene, Atrpatakan, Virq, Axvanq, Parsq, Partevstan, Nabatea,Qabakene, Elyumayis, Sogdiana, Gedrosia, Pyunikia, Hreastan): Լավագույն դեպքում ցուցակի բնակավայրերի միայն կեսն են ընկած բուն հայկական տարածքներում: Երկրորդ և Երրորդ պարամետրերը համապատասխանում են տվյալ քաղաքի x և y կոորդինատներին (-1000<=x,y<=1000): Չորրորդ պարամետրը ցույց է, թե,  որքան բնակչություն ունի հետևյալ քաղաքը(1<=p<=300000):

Հաջորդ M տողերից յուրաքանչյուրում տրված է ճանապարհի  նկարագիրը 4 պարամետրով: Առաջին երկու պարամետրերը ցույց են տալիս, թե, որ 2 քաղաքներն են միացված այդ ճանապարհով: Բոլոր ճանապարհները երկկողմանի են: Երրորդ պարամետրը ցույց է տալիս ճանապարհը ցամաքային է,թե ծովային: Ցամաքային ճանապարհը նկարագրվում է  “ _ “ նշանով, իսկ ծովայինը  “ ^ “ նշանով: Նկարագրման վերջին պարամետրը ցույց է տալիս ճանապարհի e երկարությունը (1<=e<=10^6):

Հաջորդ K տողերից յուրաքանչյուրում տրված է հակառակորդի ճամբարի  նկարագիրը 2 պարամետրով, որոնք համապատասխանում են տվյալ ճամբարի x և y կոորդինատներին (-1000<=x,y<=1000):

Ելքային տվյալներ

Եթե նշված ցուցակում պայմաններին բավարարող քաղաք կա, ապա տպեք այդ քաղաքի համարը ցուցակում, հակառակ դեպքում ”Artashatn e aynuamenayniv lavaguyn tarberaky” արտահայտությունը առանց չակերտների:

Օրինակ.

Մուտք.
4 3 1 10
25 8 30 10
Asoriq 170 -1 70000
Mec-Hayq 176 8 30000
Kapadovkia 109 15 1000
Mec-Hayq 130 20 3000
1 2 _ 5
2 3 _ 12
3 4 ^ 5
100 15
Ելք.
2

Խնդիրը պատրաստեցին Խաչատուր Դալլաքյանը և Ռոբերտ Քոչարյանը: