Cúp trưng bày

Stepan có $n$ chiếc cúp Vật lý và $m$ chiếc cúp Tin học. Mỗi chiếc cúp được mô tả bởi hai số nguyên: độ quan trọng $c$ và độ rộng $w$.

Stepan muốn trưng bày một số cúp lên một chiếc kệ có độ rộng $d$ sao cho:

• Trên kệ có ít nhất một cúp Vật lý và ít nhất một cúp Tin học.
• Tổng độ rộng của các cúp được trưng bày không vượt quá $d$.
• Với mỗi môn (Vật lý và Tin học), nếu một cúp có độ quan trọng $x$ được trưng bày thì mọi cúp của môn đó có độ quan trọng lớn hơn $x$ cũng phải được trưng bày.

Hãy tìm tổng độ quan trọng lớn nhất mà Stepan có thể đạt được. Tổng độ quan trọng là tổng độ quan trọng của tất cả các cúp được trưng bày. Nếu không có cách trưng bày nào thỏa mãn, in ra $0$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $d$ — số cúp Vật lý, số cúp Tin học và độ rộng của kệ.
• $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $c_i$ và $w_i$ — độ quan trọng và độ rộng của cúp Vật lý thứ $i$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $c_j$ và $w_j$ — độ quan trọng và độ rộng của cúp Tin học thứ $j$.

Dữ liệu ra

• In ra một số nguyên duy nhất — tổng độ quan trọng lớn nhất đạt được, hoặc $0$ nếu không thể trưng bày.

Ràng buộc

• $1\le n,m\le {10}^5$
• $1\le d\le {10}^9$
• $1\le c_i,w_i\le {10}^9$

Ví dụ