背景

    nodgd在NOI2014中跪烂了，恰好遇到了同样跪烂的lzmhhh123和liukaiwen，他们就开始回馈社会，行走江湖，行侠仗义，救世济民。

描述

    这些天他们村里受旱灾了，他们三人决定给村里一些路口挖井来缓解旱灾。
    他们村的地形可以抽象为一颗树，每个路口是树上一个节点，每条路连接两个路口。所有路口按照修建的先后顺序被编号为1,2,...,N。村里一种奇怪的迷信认为，如果第x个路口与第φ(x)个路口连接，那么会带来各种吉祥，所以村里每个村子都是严格按照这个规则修建的。其中φ是欧拉函数。
    问题是这样产生的：每个路口都需要供水，但如果每个路口都挖井显然是很耗费人力物力的事情，因为每个没有挖井的路口都可以花费一些运费到最近的路口取水，从而可能会减少总的费用。
    经过考察，他们得到了一些数据，包括挖一口井的费用cost₀，和一个路口经过k条路后到另一个路口取水的费用cost_k，他们想知道总的费用最少是多少。

输入格式

    第一行两个数N,cost₀，表示总的路口数量和挖一口井的费用。
    第二行N-1个数，第k个数表示一个路口经过k条路后到另一个路口取水的费用cost_k。

输出格式

    输出一个数，表示最小费用。

样例输入1

3 3
1 2 

样例输出1

5

样例输入2

4 1
2 3 4 

样例输出2:

4

样例解释

    样例第一组。村子的形状如图1。在2号路口挖井，1,3号都到2号节点取水，总费用为5。不存在更优的方案。

    样例第二组。村子的形状如图2。在每个路口都挖井显然是最优方案。

数据范围与约定

对于10%的数据，N<=20
对于40%的数据，N<=200
对于60%的数据，N<=2000
对于100%的数据，N<=200000，cost₀<=2000，1<=cost₁<=cost₂<=...<=cost_N-1<=10⁹。

来源

原创