你在开发一个庞大的工程，其中需要写一个拥有大量分支的函数。例如：

int calc(int x)
{
    int ans;
    if(x<=2)
    {
        if(x <= 1) ans = work1();
        else ans = work2();
    }
    else
    {
        if(x <= 3) ans = work3();
        else ans = work4();
    }
    return ans;
}

已知$x$的取值只可能是[1,2,3,4]。显然，您的程序面对每一种$x$，都需要判断两次。

但是，昨天这个函数总共被调用100次，其中90次都是$x=1$的情况，其余有8次$x=2$，1次$x=3$，1次$x=4$。为了让判断次数最少，你的最优的代码应该如下：

int calc(int x)
{
    int ans;
    if(x<=1)
        ans = work1();
    else
    {
        if(x <= 2) ans = work2();
        else
        {
            if(x<=3) ans = work3();
            else ans = work4();
        }
    }
    return ans;
}

在上述的代码中，$x=1$的情况只需要一次判断；$x=2$需要两次判断；$x=3$或$x=4$需要3次判断。付出的总判断次数是$90*1+8*2+1*1+1*1 = 108$次，不难证明，这是最低的判断次数。

现在，把这个问题抽象一下：

• 给定$n$，保证$x$一定是落在$[1,n]$内的正整数，并给出$x$为每一个数的频次。
• 只允许使用 if(x <= ***) ... else ...这一种句式。

问付出的最低判断次数。