← 返回题目列表

Codeforces · 1090/L

L. 伯兰德大学

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Berland University - 原题 PDF 第 1 页
原题PDF第17页
可复制的 PDF 提取文本
XIX Russia Team Open, High School Programming Contest
              St Petersburg, Barnaul, Tbilisi, Almaty, Kremenchug, Sochi, December 9, 2018
Problem L. Berland University

    Time limit:        1 second
    Memory limit:     512 megabytes

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

The entire course consists of n lectures. It is known that a student who visits at least k of them will pass
the course.

There are only two auditoriums in the university, one has space for a people and the other one — for b
people. To make it comfortable, the administration decided that in odd weeks the lectures will be in the
first auditorium, and in the even weeks — in the second auditorium. So the first lecture will be in the 1-st
auditorium, the second lecture in the 2-nd one, the third in the 1-st one again, and so on.

The sizes of the auditoriums are small so it might not be possible for all students to attend at least k
lectures. They ask you to count 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 minimal number of lectures to pass the course.

The limits are: 1 ≤t, n, a, b, k ≤109.

Output

Print a single integer — the maximal number of students that can attend at least k lectures and thus pass
the course.

Examples

             standard input                         standard output
 10 3 4 4 3                              4

 10 3 4 4 5                              0

 100000 100000 100000 100000 1           100000

 5 4 5 3 3                               5

 100 9 6 3 6                             7

Note

In the fourth sample, 5 students can pass the course. Here’s one possible strategy:

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

This way each of these 5 students can attend at least 3 lectures.



                                        Page 17 of 18