Ở hội chợ, người ta rao bán ~m~ món đồ chơi. Các món được đánh số lần lượt là: ~1, 2, ..., m~.

Nura muốn mua ~k~ món đồ chơi trong số đó, tuy nhiên bạn ấy chỉ có ~s~ VND (đồng Việt Nam) trong túi. Để mua các món đồ chơi này, Nura cần trả bằng đồng đô la (loại ~1~) hoặc bảng (loại ~2~). Món đồ thứ ~i~ được bán theo loại tiền ~t_i~ với giá ~c_i~.

Nura có thể mua các món đồ chơi này trong ~n~ ngày ~(1, 2, ..., n)~. Mỗi ngày, bạn ấy sẽ được biết thông tin về tỉ giá để đổi VND sang đô la và bảng. Tức là, với mỗi ngày, Nura biết được rằng ~1~ đô bằng bao nhiêu VND và ~1~ bảng bằng bao nhiêu VND.

Từ ngày ~1~ đến ~n~, mỗi ngày Nura có thể chọn mua một số món đồ chơi với tỉ giá của ngày tương ứng. Bạn ấy có thể mua bao nhiêu tuỳ thích, tuy nhiên mỗi món trong ~m~ món chỉ được mua đúng ~1~ lần trong ~n~ ngày.

Hãy giúp Nura mua được ~k~ món đồ chơi sớm nhất có thể (ngày đầu tiên Nura có đủ ~k~ món đồ là ngày có chỉ số nhỏ nhất). Biết rằng, Nura chỉ có tiền VND, và phải chuyển đổi tiền VND sang đô la hoặc bảng để mua các món đồ chơi đó.

Input

Dòng đầu tiên chứa bốn số nguyên ~n, m, k, s~ ~(1 \le n \le 2.10^5, 1\le k \le m \le 2.10^5, 1 \le s \le 10^9)~, lần lượt là số ngày, số lượng món đồ chơi được rao bán, số lượng món đồ Nura cần mua, số tiền (VND) mà Nura có.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^6)~, có ý nghĩa: ~1~ đô bằng ~a_i~ VND vào ngày thứ ~i~.

Dòng thứ ba chứa ~n~ số nguyên ~b_i~ ~(1 \le b_i \le 10^6)~, có ý nghĩa: ~1~ bảng bằng ~b_i~ VND vào ngày thứ ~i~.

~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~t_i, c_i~ ~(1 \le t_i \le 2, 1 \le c_i \le 10^6)~ - loại tiền mà món đồ thứ ~i~ được bán và giá trị của nó (theo loại tiền mà nó được bán). Nhắc lại, ~t_i = 1~ tương ứng với tiền đô, và ~t_i = 2~ tương ứng với tiền bảng.

Output

Nếu Nura không thể mua đủ ~k~ món đồ chơi, in ra -1.

Ngược lại, dòng đầu tiên chứa số nguyên ~d~ - chỉ số ngày sớm nhất mà Nura có đủ ~k~ món đồ chơi. Mỗi dòng trong ~k~ dòng tiếp theo, in ra hai số nguyên ~q_i, d_i~ - chỉ số của món đồ chơi được mua và ngày mà nó được mua. Các giá trị ~q_i~ phải phân biệt, tuy nhiên các giá trị ~d_i~ có thể trùng nhau (vì Nura có thể chọn mua nhiều món trong cùng một ngày).

Nếu có nhiều phương án, in ra phương án bất kì.

Sample 1

Input

5 4 2 2
1 2 3 2 1
3 2 1 2 3
1 1
2 1
1 2
2 2

Output

3
1 1
2 3

Sample 2

Input

4 3 2 200
69 70 71 72
104 105 106 107
1 1
2 2
1 2

Output

-1

Sample 3

Input

4 3 1 1000000000
900000 910000 940000 990000
990000 999000 999900 999990
1 87654
2 76543
1 65432

Output

-1