一堆木头棍子共有 根，每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的：
计算处理完 根棍子所需要的最短准备时间。比如，你有 根棍子，长度和宽度分别为 ，最短准备时间为 （按 的次序进行加工）。
第一行是一个整数 （）。
第二行是 个整数，分别是 。 和 的值均不超过 ，相邻两数之间用空格分开。
仅一行，一个整数，所需要的最短准备时间。
5 4 9 5 2 2 1 3 5 1 4
2
对于 的数据，，。
