Cậu em nhỏ của Marita thường bỏ bừa bãi đồ chơi trên sàn phòng khách. May mắn là Marita đã chế tạo các robot đặc biệt để dọn đồ chơi. Cô cần bạn giúp xác định robot nào dọn đồ chơi nào.

Có \(T\) đồ chơi. Đồ chơi \(i\) có trọng lượng nguyên W[i] và kích thước nguyên S[i]. Có hai loại robot:

• \(A\) robot yếu. Robot yếu \(i\) có hạn chế trọng lượng X[i], chỉ dọn được đồ chơi có trọng lượng nhỏ hơn hẳn X[i]. Kích thước đồ chơi là tùy ý.
• \(B\) robot nhỏ. Robot nhỏ \(i\) có hạn chế kích thước Y[i], chỉ dọn được đồ chơi có kích thước nhỏ hơn hẳn Y[i]. Trọng lượng đồ chơi là tùy ý.

Mỗi robot mất một phút để dọn một đồ chơi. Các robot khác nhau có thể đồng thời dọn các đồ chơi khác nhau.

Hãy xác định liệu các robot có thể dọn sạch tất cả đồ chơi hay không. Nếu có, hãy tìm thời gian nhỏ nhất để hoàn thành công việc.

Cài đặt

Bạn cần nộp một tệp cài đặt hàm C/C++ sau và phải dùng #include "robots.h":

int putaway(int A, int B, int T,
        int X[], int Y[], int W[], int S[]);

Dữ liệu vào

A là số robot yếu, B là số robot nhỏ và T là số đồ chơi. X là mảng độ dài \(A\) chứa hạn chế trọng lượng của các robot yếu; Y là mảng độ dài \(B\) chứa hạn chế kích thước của các robot nhỏ. W và S là các mảng độ dài \(T\), lần lượt chứa trọng lượng và kích thước của các đồ chơi. Chỉ số của các phần tử bắt đầu từ \(0\).

Dữ liệu ra

Hàm putaway trả về số phút nhỏ nhất cần để dọn sạch tất cả đồ chơi, hoặc \(-1\) nếu không thể dọn sạch.

Ràng buộc

• Giới hạn thời gian: 3 giây.
• Giới hạn bộ nhớ: 64 MiB.
• \(1 \le T \le 1\,000\,000\).
• \(0 \le A,B \le 50\,000\) và \(1 \le A+B\).
• \(1 \le X[i],Y[i],W[i],S[i] \le 2\,000\,000\,000\) trên các chỉ số hợp lệ của từng mảng.

Phân nhóm

Mỗi nhóm tuân theo các ràng buộc chung và các điều kiện bổ sung sau.

Trình chấm mẫu

Trình chấm mẫu đọc tệp robots.in theo định dạng:

• Dòng 1: A B T.
• Dòng 2: X[0] ... X[A-1].
• Dòng 3: Y[0] ... Y[B-1].
• \(T\) dòng tiếp theo: mỗi dòng chứa W[i] S[i], theo thứ tự \(i=0,\ldots,T-1\).

Nếu \(A=0\) hoặc \(B=0\), dòng tương ứng (dòng 2 hoặc dòng 3) là dòng rỗng.

Ví dụ

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

3

A = 2
B = 1
T = 3
X = [2, 5]
Y = [2]
W = [3, 5, 2]
S = [1, 3, 2]

-1