Ցորենի դաշտ
Դաշտային մկների մոտ իրարանցում է։ Տագնապ է հնչել, և նրանք բոլորը պետք է շտապ դուրս գան դաշտից։ Պարզության համար համարենք, որ ցորենի դաշտը ուղղանկյունաձև է և տրոհված է վանդակների։ Մկները կարող են մի վանդակից անցնել ընդհանուր կողմով հարևան չորս վանդակներից ցանկացածին, եթե բավականաչափ համարձակություն ունեն։ Վանդակներից յուրաքանչյուրն ունի այնտեղ աճող բուսականության խտության աստիճան, որը դրական ամբողջ թիվ է։ Յուրաքանչյուր մկնիկ ունի համարձակության աստիճան, որը նույնպես դրական ամբողջ թիվ է։ Մկնիկը կարողանում է անցնել հարևան վանդակ, եթե այդ վանդակի խտության աստիճանը չի գերազանցում իր համարձակության աստիճանին։ Դաշտից դուրս գալու համար բավական է հասնել նրա եզրերից որևէ մեկին։ Եթե երկու մկնիկ հանդիպում են իրար, պակաս անվախը սկսում է շարժվել ավելի քաջի հետևից և լինել այնպիսի վանդակներում, որտեղ միայնակ չէր կարող գնալ։
Պույ-պույը եզրակացրեց, որ նույնիսկ իրար օգնելով, հնարավոր է, որ ոչ բոլորը կարողանան դուրս գալ դաշտից։ Այ, եթե իրենք ավելի համարձակ լինեին, թերևս բոլորին դա կհաջողվեր։ Հարց է առաջանում, առնվազն ի՞նչ D մեծությամբ է պետք ավելացնել բոլորի համարձակության աստիճանը, այսինքն, որ i-րդ մկնիկի համարձակության աստիճանը դառնա
Օգնեք Պույ-պույին գտնելու, այդ մինիմալ D-ն։
Մուտքային տվյալներ
Առաջին տողում տրված են են երեք բնական N, M (3 ≤ N, M ≤ 1000) և K (1 ≤ K ≤ N*M) թվեր՝ դաշտի չափսերը և մկնիկների թիվը։ Հաջորդ N տողերում տրված են M դրական ամբողջ թվեր՝ վանդակների խտությունները։ Վերջին K տողերից յուրաքանչյուրը պարունակում է 3 բնական
և թվեր՝ i-րդ մկնիկի դիրքը և նրա համարձակության աստիճանը։ Երաշխավորվում է, որ համապատասխան վանդակում խտությունը Ելքային տվյալներ
Ելքում արտածեք մեկ թիվ՝ D-ի մինիմալ արժեքը։
Օրինակ
Մուտք | Ելք |
5 10 5
5 5 5 5 7 2 2 2 2 2
5 1 1 1 7 1 1 1 1 2
5 1 6 6 7 4 5 5 5 5
5 1 6 1 7 1 5 1 1 2
5 5 6 5 7 5 5 2 2 2
4 6 1
2 9 2
4 9 1
4 4 2
2 3 4 | 2 |
Բացատրություն
Շատ վատ է (4,4) վանդակում գտնվող մկնիկի վիճակը, շրջակա բոլոր վանդակներում խտությունը մեծ է։ Բայց նրան կարող է օգնության հասնել (2,3) վանդակում գտնվող և 4 համարձակության աստիճան ունեցող մկնիկը, միայն թե դրա համար նրա համարձակությունը պետք է մեծացնել 2-ով։ Այդ դեպքում (2,9) վանդակում գտնվող մկնկն էլ կկարողանա օգնության հասնել և դաշտից դուրս բերել (4,6) վանդակում գտվնող մկնկիկին, որի համարձակությունը 1 է։ Իսկ 3-րդ մկնիկը (4,9) վանդակից կարողանում է ներքև գնալ և դուրս գալ, եթե D=2:
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակը,
- Ենթախնդիր 1 (10 միավոր)
, բոլոր վանդակները, որոնցում ի սկզբանե մկնիկներ չկան, ունեն հավասար խտություն
- Ենթախնդիր 2 (20 միավոր)
, երաշխավորում է, որ
- Ենթախնդիր 3 (10 միավոր)
, երաշխավորում է, որ
- Ենթախնդիր 4 (15 միավոր)
, գոյություն ունի լուծում, որտեղ ամբողջ խումբը հավաքվում և դուրս է գալիս մեկ վայրից, ընդ որում
- Ենթախնդիր 5 (10 միավոր)
, գոյություն ունի լուծում, որտեղ ամբողջ խումբը հավաքվում և դուրս է գալիս մեկ վայրից,
- Ենթախնդիր 6 (20 միավոր)
, երաշխավորում է, որ
- Ենթախնդիր 7 (15 միավոր)Լրացուցիչ սահմանափակումներ չկան:
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB