Arxivchi

Masala tavsifi

Yer orbitasidagi Arxiv-Serverda ketma-ket joylashgan $N$ ta modul mavjud. Har bir modul ichida noma'lum butun qiymat saqlangan: $p_1, p_2, \ldots, p_N$

Husanboy ushbu qiymatlarning barchasini bilib olmoqchi, lekin xavfsizlik tizimi sababli modullar ichidagi qiymatlarni to'g'ridan-to'g'ri ko'rish mumkin emas. Server faqat quyidagi turdagi ma'lumotni pullik tarzda beradi:

Agar Husanboy $i$ va $j$ ni tanlasa ($1 \le i \le j \le N$), server unga $[i, j]$ oralig'idagi qiymatlar yig'indisini aytadi: $p_i$

Buning evaziga Husanboy $C(i, j)$ miqdorda "kredit" to'laydi.

Husanboy istagancha so'rov berishi mumkin. Uning maqsadi --- sotib olingan yig'indilar yordamida barcha $p_1, p_2, \ldots, p_N$ qiymatlarni aniq tiklash va buning uchun to'lanadigan umumiy narxni minimal qilish.

Input Format

Birinchi qatorda bitta natural son $N$ $(1 \le N \le 1\,000)$ beriladi.

Keyingi $N$ ta qatorda so'rov narxlari beriladi: $i+1$-qatorda $N-i+1$ ta natural son bo'ladi --- ketma-ket ravishda $C(i,i), C(i,i+1), \ldots, C(i,N)$.

Cheklovlar:

$1 \le i \le j \le N$

$0 \le C(i,j) \le 10^6$

Output Format

Bitta son chiqaring --- Husanboy $p$ massivining barcha elementlarini aniqlash uchun to'lashi kerak bo'lgan minimal umumiy narx.

Scoring

3
5 5 1
5 2
5

8