Մատրիցների բազմապատկում

Տրված են n մատրիցներ , որոնց չափերն են համապատասխանաբար։ Մատրիցները դասավորված են ձախից աջ, 1-ից մինչև n: Թույլատրելի է փակագծեր տեղադրել՝ որոշ բազմապատկումներ նախապատվությամբ կատարելու համար։

Ո՞րն է բոլոր մատրիցները բազմապատկելու համար անհրաժեշտ գործողությունների նվազագույն քանակը:

Մուտք

Մուտքի առաջին տողում տրված է n ամբողջ թիվը ()։

Հաջորդ n տողերում տրված են յուրաքանչյուր մատրիցի և չափերը (1 ≤ ≤ 1000)։

Ենթադրվում է, որ բոլոր i ∈ {1, 2, ..., n-1}-երի համար։

Ելք

Հարկավոր է տպել բոլոր մատրիցները բազմապատկելու համար պահանջվող նվազագույն գործողությունների քանակը:

Օրինակներ