در کشور تمبرآباد، نه تلفن وجود دارد، نه تلگراف، نه فکس و نه اینترنت، بنابراین مردم تمام کارهایشان را از طریق ارسال نامه انجام می‌دهند. این کشور $n$ شهر دارد که روی یک خط مستقیم قرار دارند و به ترتیب با شماره‌های $1$ تا $n$ شماره‌گذاری شده‌اند. می‌دانیم به ازای هر $1 < i \leq n$ شهرهای $i$ام و $i-1$ همسایه محسوب می شوند.
مصطفی به تازگی وزیر پست کشور شده و می‌خواهد برای توزیع تمبر بین شهرهای مختلف در $t$ روز آینده تصمیم گیری کند. او می‌داند که شهر $i$ام در روز $j$ام به $a_{j,i}$ تمبر احتیاج دارد و پس از آن دیگر نمی‌تواند دوباره از تمبرهای استفاده شده استفاده کند. همچنین می‌داند که در روز اول، تعداد تمبرهای موجود در شهر $i$ برابر با $b_i$ می‌باشد. سیستم انتقال تمبر بین شهرها به این صورت است که در پایان هر روز، هر شهر می‌تواند تعدادی از تمبرهای استفاده نشده خود را به شهرهای همسایه خود ارسال کند. مساله اینجاست که وزارت حمل‌و‌نقل می‌خواهد حداکثر تعداد تمبرهایی که لازم می‌شود در پایان یک روز از هر شهر خارج شود را کمینه کند، به همین دلیل از مصطفی خواسته کم‌ترین عدد $k$ را پیدا کند که بتوان برنامه انتقال تمبر بین شهرها را تنظیم کرد، طوری که در هر روز حد اکثر $k$ تمبر از هر شهر خارج شود و در هر یک از $t$ روز آینده همه‌ی شهرها برای انجام کار های خود به تعداد کافی تمبر داشته باشند.
شما باید برنامه‌ای بنویسید تا با دریافت اطلاعات مربوط به سوال کم‌ترین عدد $k$ را به‌دست آورد. می توانید اطمینان داشته باشید که در صورتی که مقدار $k$ به اندازه کافی زیاد باشد؛ می توان طوری برنامه انتقال تمبرها را چید که هیچ شهری در هیچ روزی بدون تمبر نماند.
خروجی تنها باید شامل یک عدد صحیح باشد که برابر با مقدار کمینه $k$ است.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 2 3 3 3 1 1 1 2 2 2 | 0 |
| 3 2 1 7 1 1 1 1 2 2 2 | 4 |