问题描述

有一个人前来买瓜
但是他没有带钱，他想用钢条支付瓜钱
他有一根长为$l$米的钢条，他可以将这根钢条切分为整数长度的几段
设长为$n$米的钢条价值为$p_i$
求华强最多能买几斤瓜

数据

输入

第一行含有个整数$l$, ($1 ≤ l ≤ 10^4$) 代表钢条最长长度
第二行有l个整数$p_i$, ($1 ≤ p_i ≤ 10^6$) 代表长为$p_i$的钢管能卖多少钱
第三行是一个整数$n$, ($1 ≤ n ≤ 10^5$) 代表有$n$组查询
之后有$n$行，含有一个整数$x$, ($1 ≤ x ≤ l$)代表钢条的长度，一个整数$y$, ($1 ≤ y ≤ 1000$)代表西瓜$y$元一斤

输出

一个整数n，代表最多能买n斤西瓜

样例

10
1 5 8 9 10 17 17 20 24 30
2
10 2
8 1

15
22