Codeforces Round #471 (Div. 2) A. Feed the cat B. Not simply beatiful strings

After waking up at hh:mm, Andrew realised that he had forgotten to feed his only cat for yet another time (guess why there's only one cat). The cat's current hunger level is H points, moreover each minute without food increases his hunger by D points.

At any time Andrew can visit the store where tasty buns are sold (you can assume that is doesn't take time to get to the store and back). One such bun costs C roubles and decreases hunger by N points. Since the demand for bakery drops heavily in the evening, there is a special 20% discount for buns starting from 20:00 (note that the cost might become rational). Of course, buns cannot be sold by parts.

Determine the minimum amount of money Andrew has to spend in order to feed his cat. The cat is considered fed if its hunger level is less than or equal to zero.

Input

The first line contains two integers hh and mm (00 ≤ hh ≤ 23, 00 ≤ mm ≤ 59) — the time of Andrew's awakening.

The second line contains four integers H, D, C and N (1 ≤ H ≤ 105, 1 ≤ D, C, N ≤ 102).

Output

Output the minimum amount of money to within three decimal digits. You answer is considered correct, if its absolute or relative error does not exceed 10 - 4.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if $\text{[math]}$ .

Examples

input

Copy

19 00
255 1 100 1

output

25200.0000

input

Copy

17 41
1000 6 15 11

output

1365.0000

Note

In the first sample Andrew can visit the store at exactly 20:00. The cat's hunger will be equal to 315, hence it will be necessary to purchase 315 buns. The discount makes the final answer 25200 roubles.

In the second sample it's optimal to visit the store right after he wakes up. Then he'll have to buy 91 bins per 15 roubles each and spend a total of 1365 roubles.

这是个大水题，比较一下直接去和等到八点去哪个省钱注意判断一下如果时间在八点之后直接算就好了

#include<bits/stdc++.h>

using namespace std;

int hh,mm,h,d,c,n;
int cnt1,cnt2,m1,h1,t;

int main()
{
    double sum1,sum2;
    sum1=sum2=99999999;
    scanf("%d %d %d %d %d %d",&hh,&mm,&h,&d,&c,&n);
    if(hh<20)
    {

        if(h%n) cnt1=h/n+1;
        else cnt1=h/n;
        sum1=cnt1*c;
        if(0>=mm)
            m1=0-mm;
        else
        {
            m1=60-mm;
            hh=hh+1;
        }
        t=m1+(20-hh)*60;
        h1=h+t*d;
        if(h1%n) cnt2=h1/n+1;
        else cnt2=h1/n;
        sum2=cnt2*c*0.8;
    }
    else
    {
        if(h%n) cnt1=h/n+1;
        else cnt1=h/n;
        sum1=cnt1*c*0.8;
    }
    double sum=min(sum1,sum2);
    printf("%.4lf
",sum);
    return 0;
}

View Code

Let's call a string adorable if its letters can be realigned in such a way that they form two consequent groups of equal symbols (note that different groups must contain different symbols). For example, ababa is adorable (you can transform it to aaabb, where the first three letters form a group of a-s and others — a group of b-s), but cccc is not since in each possible consequent partition letters in these two groups coincide.

You're given a string s. Check whether it can be split into two non-empty subsequences such that the strings formed by these subsequences are adorable. Here a subsequence is an arbitrary set of indexes of the string.

Input

The only line contains s (1 ≤ |s| ≤ 105) consisting of lowercase latin letters.

Output

Print «Yes» if the string can be split according to the criteria above or «No» otherwise.

Each letter can be printed in arbitrary case.

Examples

input

Copy

ababa

output

Yes

input

Copy

zzcxx

output

Yes

input

Copy

yeee

output

No

Note

In sample case two zzcxx can be split into subsequences zc and zxx each of which is adorable.

There's no suitable partition in sample case three.

这个题目对题意理解有点要求，他需要的找的是，把字符串分成两个子串，每个子串都要“adorable”，就是说只能由两个字母组成，稍微分析一下，只有字母种类t为2 3 4且字符串长度大于3才行，然后分类，t=2的，每个字母大于2就行了，t=3的有一个字母大于2就行了，t4，怎么样都可以。

#include<bits/stdc++.h>

using namespace std;

char s[100005];
int a[100005],cnt=0;
char t[100005]= {0};

int main()
{
    cin>>s;
    int f=0;
    if(strlen(s)<=3) f=0;
    else
    {
        for(int i=0; i<strlen(s); i++)
        {

            if(!a[s[i]])
            {
                t[cnt]=s[i];
                cnt++;
                if(cnt>=5) break;
            }
            a[s[i]]++;
        }
        if(cnt<=1 || cnt>=5) f=0;
        if(cnt==4) f=1;
        if(cnt==2)
            if(a[t[0]]>=2 && a[t[1]]>=2) f=1;
        if(cnt==3)
            if(a[t[0]]>=2 || a[t[1]]>=2 || a[t[2]]>=2) f=1;
    }
    if(f) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

View Code