作为一个写程序的，小灰灰时常需要管理他的电脑资源。

具体来说，小灰灰面前有 种资源，其中第 种资源有 份。

作为一个写文章的，小蓝并不在意这些资源，她只会不断地提出新的请求。

具体来说，小蓝共有 个请求，其中第 个请求是申请使用第 和第 之间的所有电脑资源，每种资源都需要 份。

由于小蓝不会规划她的申请，所以她的申请可能并不合理，这样就会导致有时候电脑资源不足，从而无法响应小蓝的请求。

比如：

- 总共有 种资源，它们的数量分别是
- 小蓝提出的第 个请求是申请第 到第 种电脑资源各 份
- 电脑响应了这个请求，此时它剩余的资源是
- 小蓝提出的第 个请求是申请第 到第 种电脑资源各 份
- 此时电脑就会拒绝响应这个请求并且直接卡死，因为剩余资源不足以完成小蓝的申请

小灰灰发现了这个悲剧，他能够很快的计算出小蓝在第几次申请时会被卡死。然而，小蓝为了避免卡死，她打算买一个新的电脑配件，帮助她增加自己的电脑资源……

小蓝有 种想买的电脑配件，第 种配件可以使得第 和第 之间的所有电脑资源增加 份。

为了帮助小蓝挑选到最合适的电脑配件，小灰灰计划对每一种电脑配件都计算出，如果选择这个电脑配件，小蓝在进行第几次申请时会发生卡死现象。

第一行输入三个空格分隔的整数，分别代表  和 。

接下来一行  各空格分隔的整数，分别代表  到 。

接下来  行，第  行输入三个空格分隔的整数，分别代表  和 。

接下来  行，第  行输入三个空格分隔的整数，分别代表  和 。

保证：



 

输出共  行，第  行一个整数代表如果选用第  种电脑配件，小蓝遇见卡死现象是因为第几次申请。

特别的，如果小蓝可以完成所有的申请操作，请输出 。

5 3 3
5 3 9 6 3
2 5 2
1 5 5
1 2 1
1 5 100
1 5 0
2 5 4

-1
2
3

本题时限较为宽裕，不存在卡常的情况，请确定你的算法不会被卡常。