Giới hạn thời gian

Điểm: 3,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Valera đang chuẩn bị ra đề một bài tập, và cần chọn giới hạn thời gian (TL) cho bài đó.

Valera đã viết $n$ lời giải đúng, lời giải đúng thứ $i$ có thời gian chạy là $a_{i}$ giây. Anh cũng viết $m$ lời giải sai, lời giải sai thứ $j$ có thời gian chạy là $b_{j}$ giây.

Giả sử Valera đặt giới hạn thời gian là $v$ giây. Khi đó:

Một lời giải vượt qua chấm hệ thống nếu thời gian chạy của nó không quá $v$ giây.
Một lời giải vượt qua chấm hệ thống với thời gian dư nếu thời gian chạy $a$ của nó thỏa mãn $2 a \leq v$ .

Hãy tìm giá trị $v$ thỏa mãn đồng thời các điều kiện sau:

$v$ là số nguyên dương.
Tất cả các lời giải đúng đều vượt qua chấm hệ thống.
Có ít nhất một lời giải đúng vượt qua chấm hệ thống với thời gian dư.
Tất cả các lời giải sai đều không vượt qua chấm hệ thống.
$v$ là nhỏ nhất trong các giá trị thỏa mãn các điều kiện trên.

Nếu không tồn tại $v$ phù hợp, in $- 1$ .

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ .
Dòng thứ hai chứa $n$ số nguyên dương $a_{1}, a_{2}, \dots, a_{n}$ — thời gian chạy của các lời giải đúng.
Dòng thứ ba chứa $m$ số nguyên dương $b_{1}, b_{2}, \dots, b_{m}$ — thời gian chạy của các lời giải sai.

Dữ liệu ra

In ra giá trị $v$ thỏa mãn, hoặc $- 1$ nếu không tồn tại.

Ràng buộc

$1 \leq n, m \leq 100$
$1 \leq a_{i}, b_{j} \leq 100$

Ví dụ

Input	Output	Giải thích
3 6 4 5 2 8 9 6 10 7 11	5	Với $v = 5$ : max $a = 5 \leq 5$ , có $a = 2$ thỏa $2 \cdot 2 = 4 \leq 5$ , và mọi $b_{j} \geq 6 > 5$ .
3 1 3 4 5 6	-1	Cần $v \geq 5$ (max $a$ ) và $v \geq 2 \cdot 3 = 6$ (để có lời giải dư thời gian), nhưng cũng cần $v < 6$ (để $b = 6$ trượt). Vô lý.

Bình luận

Không có bình luận tại thời điểm này.