20. Ms. Weasel eats chicken

黄鼠狼姐姐将要踏上一段旅程。她事先规划好了她的旅行线路，因此她知道她将从小镇 $0$ 出发，途径小镇 $1,2\dots n-1$，最终到达小镇 $n$。

出发时，黄鼠狼姐姐的体力值为 $S$。在从小镇 $i-1$ 前往小镇 $i$ 的路途当中，她会消耗体力 $w_i$。

到达小镇 $i$ 后，她可以在这个小镇的饭馆吃一些鸡来恢复体力。由于近几年经济不景气，外加东方神秘力量（据说是鸡年）的影响，每个小镇都只能供应 $1$ 只鸡，并使黄鼠狼姐姐恢复 $x$ 点体力。每个小镇鸡的价格是不同的：小镇 $i$ 中每只鸡的价格为 $P_i$。

黄鼠狼姐姐希望花费尽可能少的钱走完整个旅程。如果黄鼠狼姐姐在某一时刻体力值小于 $0$，她会饿死在半路上。