Fulfillment of Warehouse Orders

You are given the initial stock of a warehouse and a list of orders. Each order consists of a required quantity of each product. For every order, if the current stock is sufficient to fulfill it, reduce the stock accordingly. Otherwise, the order cannot be fulfilled.

Your task is to determine the 1-based index of the first unfulfillable order. If all orders can be fulfilled, output -1.

Formally, let \(w_i\) denote the stock of product \(i\) in the warehouse and an order be represented by \(o_{i}\) for each product \(i\). For each order, if \(o_{i} \leq w_i\) for all products \(i\), then update \(w_i \gets w_i - o_{i}\). Otherwise, output the current order's index (starting from 1). If all orders are processed successfully, output \(-1\).

inputFormat

The input is read from stdin in the following format:

1. An integer \(n\), representing the number of products.
2. \(n\) space-separated integers, representing the available stock in the warehouse.
3. An integer \(m\), representing the number of orders.
4. Next \(m\) lines: each line contains \(n\) space-separated integers which represent the required quantities for that order.

outputFormat

Output to stdout a single integer: the 1-based index of the first order that cannot be fulfilled, or \(-1\) if all orders can be fulfilled.

3
10 5 8
3
2 1 3
5 2 2
3 2 1

-1