Vận chuyển


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Tuấn là quản lí của một Công ty chuyên vận chuyển hàng hóa liên tỉnh bằng đường bộ. Công ty cần chuyến một gói hàng từ Hà Nội đến Sài Gòn, do không có chuyến chuyển thẳng từ Hà Nội đến Sài Gòn mà phải qua trạm trung chuyển tại Huế.

Có $N$ chuyến vận chuyển hàng từ Hà Nội đến Huế, chuyến thứ $i$ xuất phát vào thời điểm $a_i$, và các chuyến vận chuyển đều có thời gian là $T_a$.

Có $M$ chuyến vận chuyển từ Huế đến Sài Gòn, chuyến thứ $j$ xuất phát vào thời điểm $b_j$ và các chuyến vận chuyển đều có thời gian là $T_b$.

Nếu công ty sử dụng chuyến vận chuyển thứ $i$ xuất phát từ Hà Nội đến Huế, sau đó sử dụng chuyến vận chuyển thứ $j$ xuất phát từ Huế đến Sài Gòn thì phải thỏa mãn $b_j\ge a_i+T_a$.

Công ty luôn muốn chọn phương án vận chuyển để gói hàng có thể đến Sài Gòn sớm nhất. Tuy nhiên, vì gói hàng bị lỗi nên Tuấn lại muốn gói hàng không thể đến được nơi nhận nhằm mục đích khôi phục lỗi hoặc nếu luôn tồn tại cách vận chuyển gói hàng đến Sài Gòn thì phải đến muộn nhất có thể để Tuấn tăng thêm thời gian xử lý. Tuấn được phép hủy tối đa $K$ chuyến vận chuyển trong tất cả $N+M$ chuyến để thực hiện mong muốn trên.

Hãy xác định thời điểm gói hàng đến Sài Gòn khi Tuấn hủy các chuyến vận chuyển khiến gói hàng đến muộn nhất có thể hoặc thông báo gói hàng không thể đến được nơi nhận.

Dữ liệu

  • Dòng đầu tiên gồm 5 số nguyên dương $N, M, T_a, T_b, K \ (1\le N,M \le 10^6; 1\le T_a,T_b\le 10^9; 0\le K \le N+M)$;
  • Dòng thứ hai gồm $N$ số nguyên dương $a_i \ (1\le a_1 \le a_2 \le ... \le a_N \le 10^9)$;
  • Dòng thứ ba gồm $M$ số nguyên dương $b_i \ (1\le b_1 \le b_2 \le ... \le b_N \le 10^9)$.

Kết quả

  • Một số nguyên là thời điểm gói hàng đến nơi nhận khi Tuấn hủy các chuyến vận chuyển gói hàng đến Sài Gòn muộn nhất có thể hoặc thông báo gói hàng không thể đến nơi được. Nếu gói hàng không thể đến nơi được thì ghi -1.

Chấm điểm

60; $1\le N,M \le 10^6; 1\le T_a, T_b \le 10^6$. 40; Không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

input

4 5 1 1 2
1 3 5 7
1 2 3 9 10

output

11
Ví dụ 2

input

2 2 4 3
1 10
10 20

output

-1
Ví dụ 3

input

4 4 2 2 1
1 2 3 4
6 7 8 15

output

9

Comments

There are no comments at the moment.