Start 2022-08-01 11:32:12

20220801SeniorTest

End 2022-08-02 00:00:00
Contest is over.
Now 2026-11-19 00:40:45

C. 治疗病人(cure)

Description

话说凯妹建立八院以来,八院名气越来越响,以致五湖四海的病人慕名而来(囧。)恰好一天来了m位病人,使一位病人的健康程度变为x需花费ax2元(每位病人的健康程度必须为正整数)。由于人手不够,凯妹还需要n位医生,每个医生负责治疗一些病人,这些病人的健康程度之和不能超过该医生的能力值y,凯妹雇佣一位能力值为y的医生需花费by2元。每位病人都需要有医生负责。由于凯妹秉承着“一切从病人利益出发”的观念,他想知道使所有病人健康程度之和至少为k至少需花费几元。

Input

一行五个正整数n、m、k、a、b,如题目描述。n<=m<=k。

Output

一行一个正整数表示最小花费。

Examples

Input

2 4 100 2 5

Output

30000

Input

2 3 100 1 1

Output

8572

Hint

本题10个测试点数据范围有如下约定

1 :1<=n、m、k<=5

2 :1<=n、m、k<=20

3 :1<=n、m、k<=40

4 :1<=n、m、k<=80

5 :1<=n、m、k<=100

6 :1<=n、m、k<=400

7 :1<=n、m、k<=1000000,m%n=1

8 :1<=n、m、k<=1000000

9 :1<=m、k<=1000000,n=1

10 :1<=n、m、k<=1000000,m%n=0

对于全部测试点1<=a,b<=10^6


Submit

Login

Signup
Time Limit 2 seconds
Memory Limit 256 MB
Submit