Berland University

Time limit1sMemory limit512 MB

Summary

Given t students, n lectures alternating between two auditoriums of sizes a and b, and a passing threshold k, find the maximum number of students who can each attend at least k lectures.

Level: Medium6 of 10
Topics: Binary search, Greedy, Math, Implementation
Solved: No attempts yet

Statement

There are $t$ students at the best university in Berland. They only study programming in Berland, so there is only one subject. Every student must attend the lectures.

The whole course consists of $n$ lectures. A student who attends at least $k$ of them passes the course.

The university has only two auditoriums, one with space for $a$ people and the other for $b$ people. To keep things comfortable, the administration decided that in odd weeks the lectures will be in the first auditorium, and in even weeks in the second auditorium. So the first lecture is in auditorium 1, the second lecture in auditorium 2, the third in auditorium 1 again, and so on.

The auditoriums are small, so it may be impossible for all students to attend at least $k$ lectures. Find the maximum number of students that can pass the course.

Input

The first line contains five integers:

$t$ --- the number of students;
$n$ --- the number of lectures;
$a$ --- the size of the first auditorium;
$b$ --- the size of the second auditorium;
$k$ --- the minimum number of lectures needed to pass the course.

The limits are $1 \leq t, n, a, b, k \leq 10^9$ .

Output

Print a single integer: the maximum number of students that can attend at least $k$ lectures and pass the course.

Hint

In the fourth sample, 5 students can pass the course. One possible strategy is:

Students $1$ , $2$ , $3$ , $4$ , $5$ attend the first lecture.
Students $1$ , $3$ attend the second lecture.
Students $1$ , $2$ , $3$ , $4$ , $5$ attend the third lecture.
Students $2$ , $4$ , $5$ attend the fourth lecture.

This way each of these 5 students attends at least $3$ lectures.

Examples5

Example 1
Input
```
10 3 4 4 3
```
Expected output
```
4
```
Example 2
Input
```
10 3 4 4 5
```
Expected output
```
0
```
Example 3
Input
```
100000 100000 100000 100000 1
```
Expected output
```
100000
```
Example 4
Input
```
5 4 5 3 3
```
Expected output
```
5
```
Example 5
Input
```
100 9 6 3 6
```
Expected output
```
7
```