植物園高級中學是全國首屈一指的名校，其設立目的旨在培育肩負國家未來的重要人才。而這所中學的畢業生，無論是升學或是就業均有受到保障，要進入頂尖的大學或企業都易如反掌。

然而由於是高手的聚集地，這所學校內部的競爭壓力也是高的驚人。尤其是這所學校中途退學的機制，讓學生想要在這裡安然無事的度過三年畢業，可說是難如登天。

你是植物園高級中學的學生之一，而學校剛舉行了第一次的定期考試。這個考試有個特殊的規定，那就是只要一個學生有任何一個科目不及格，那麼他就得接受中途退學的懲罰。及格的定義是該科成績達全班成績平均值的一半。

你的班上有$N$位同學（包含你），編號為$1$到$N$，進行了一場總分為$C$分的定期考試，所有人的分數皆為$0$到$C$之間的整數。等到考試的成績一揭曉，就可能有人必須退學。

不過神通廣大的你，在分數正式公布前，早已事先得知了全班每個人的成績，其中第$i$號的人成績為$s_i$。而且根據你所知道的消息，在這所學校裡，有十萬零八千種以上的方法，可以讓一個人的分數上升或下降。當然，這麼做必須付出一定的代價，而且每個人的代價也不盡相同。根據你的資料，對於第$i$個人，使他的成績每上升一分，就必須付出$a_i$的代價；而使他的成績每下降一分，就必須付出$b_i$的代價。不過每個人的成績最後都必須落在$0$到$C$分之間，否則是不合法的。

你希望使全班的所有同學都平安度過這次的定期考試，但又不希望付出太多代價。求欲使所有人皆及格所需付出的代價最小值是多少。