说明

一段长为n的绳子，可以切成很多段，并且有好几种切法，比如当n=4时，可以切成1 1 1 1， 1 1 2，1 3，2 2。

而每种长度有不同的价格。现在给定n，和每种长度绳子的价格，要求输出能切出的最大价格。

输入格式

输出格式

每个测试输出占一行

2
1 3
3
2 3 4

3
6

来源