---

Time limit : 2sec / Memory limit : 256MB

Score : 300 points

Problem Statement

You've come to your favorite store Infinitesco to buy some ice tea.

The store sells ice tea in bottles of different volumes at different costs. Specifically, a 0.25-liter bottle costs Q yen, a 0.5-liter bottle costs H yen, a 1-liter bottle costs S yen, and a 2-liter bottle costs D yen. The store has an infinite supply of bottles of each type.

You want to buy exactly N liters of ice tea. How many yen do you have to spend?

Constraints

• 1≤Q,H,S,D≤108
• 1≤N≤109
• All input values are integers.

---

Input

Input is given from Standard Input in the following format:

Q H S D
N

Output

Print the smallest number of yen you have to spend to buy exactly N liters of ice tea.

---

Sample Input 1

20 30 70 90
3

Sample Output 1

150

Buy one 2-liter bottle and two 0.5-liter bottles. You'll get 3 liters for 90+30+30=150 yen.

---

Sample Input 2

10000 1000 100 10
1

Sample Output 2

100

Even though a 2-liter bottle costs just 10 yen, you need only 1 liter. Thus, you have to buy a 1-liter bottle for 100 yen.

---

Sample Input 3

10 100 1000 10000
1

Sample Output 3

40

Now it's better to buy four 0.25-liter bottles for 10+10+10+10=40 yen.

---

Sample Input 4

12345678 87654321 12345678 87654321
123456789

Sample Output 4

1524157763907942

#include <iostream>  
#include <algorithm>  
#include <cstring>  
#include <cstdio>  
#include <vector>  
#include <queue>  
#include <stack>  
#include <cstdlib>  
#include <iomanip>  
#include <cmath>  
#include <cassert>  
#include <ctime>  
#include <map>  
#include <set>  
using namespace std;  
#define lowbit(x) (x&(-x))  
#define max(x,y) (x>=y?x:y)  
#define min(x,y) (x<=y?x:y)  
#define MAX 100000000000000000  
#define MOD 1000000007  
#define pi acos(-1.0)  
#define ei exp(1)  
#define PI 3.141592653589793238462  
#define ios() ios::sync\_with\_stdio(false)  
#define INF 1044266558  
#define mem(a) (memset(a,0,sizeof(a)))  
typedef long long ll;  
ll a\[\],n;  
int main()  
{  
    while(scanf("%lld%lld%lld%lld",&a\[\],&a\[\],&a\[\],&a\[\])!=EOF)  
    {  
        scanf("%lld",&n);  
        for(int i=;i<;i++) a\[i\]=min(a\[i\],\*a\[i-\]);  
        printf("%lld\\n",n/\*a\[\]+(n&)\*a\[\]);  
    }  
    return ;  
}

---

Time limit : 2sec / Memory limit : 256MB

Score : 500 points

Problem Statement

You have a string A=_A_1_A_2…A__n consisting of lowercase English letters.

You can choose any two indices i and j such that 1≤i≤j≤n and reverse substring A__i__A__i+1…A__j.

You can perform this operation at most once.

How many different strings can you obtain?

Constraints

• 1≤|A|≤200,000
• A consists of lowercase English letters.

---

Input

Input is given from Standard Input in the following format:

A

Output

Print the number of different strings you can obtain by reversing any substring in A at most once.

---

Sample Input 1

aatt

Sample Output 1

5

You can obtain aatt (don't do anything), atat (reverse A[2..3]), atta (reverse A[2..4]), ttaa (reverse A[1..4]) and taat (reverse A[1..3]).

---

Sample Input 2

xxxxxxxxxx

Sample Output 2

1

Whatever substring you reverse, you'll always get xxxxxxxxxx.

---

Sample Input 3

abracadabra

Sample Output 3

44
预处理。

#include <iostream>  
#include <algorithm>  
#include <cstring>  
#include <cstdio>  
#include <vector>  
#include <queue>  
#include <stack>  
#include <cstdlib>  
#include <iomanip>  
#include <cmath>  
#include <cassert>  
#include <ctime>  
#include <map>  
#include <set>  
using namespace std;  
#define lowbit(x) (x&(-x))  
#define max(x,y) (x>=y?x:y)  
#define min(x,y) (x<=y?x:y)  
#define MAX 100000000000000000  
#define MOD 1000000007  
#define pi acos(-1.0)  
#define ei exp(1)  
#define PI 3.141592653589793238462  
#define ios() ios::sync\_with\_stdio(false)  
#define INF 1044266558  
#define mem(a) (memset(a,0,sizeof(a)))  
typedef long long ll;  
ll a\[\]\[\],ans;  
char s\[\];  
int main()  
{  
    while(scanf("%s",s+)!=EOF)  
    {  
        memset(a,,sizeof(a));  
        int len=strlen(s+);  
        ans=;  
        for(int i=;i<=len;i++)  
        {  
            for(int j=;j<;j++)  
                a\[i\]\[j\]=a\[i-\]\[j\];  
            a\[i\]\[s\[i\]-'a'\]++;  
        }  
        for(int i=;i<=len;i++)  
            ans+=len-i-a\[len\]\[s\[i\]-'a'\]+a\[i\]\[s\[i\]-'a'\];  
        printf("%lld\\n",ans+);  
    }  
    return ;  
}