某公司目前推出了N个在售的金融产品（1<N≤100），对于张三，我们用a,表示他购买了a；（0≤a<104）单位份额的第价个产品(1≤14N），现给出K（1<K<N）个方蜜，通过这些方室，能够支持将多个不同的产品进行整合（也可以对单个产品进行优化）形成新的产品，新的产品形成后，然用户持有了组成新产品所需的全部的原产品份额，则能够将用户持有的原产品份额转换为新产品的份额，各顺产届份额与新产品份额比例均为1:1。 我们保证，对于德个产品最多存在一个方窑使用旧产品整合成该产品，并且根据方案产出的新产品的产品编号均大于各旧产品的产品病写，现就划根据这些方基，帮助部分原升级到绿新产品的用户对产品进行升级。清协助工作人员计算当前用户能够转深出的最新产品的期的最大值.|输入描述 第一行包含整数N.第二行包含N个整数ai。第三行包含整数K。 接下来的K行，每一行代表一个方案，每一行包含整数L和M(M>1），L为该方窒产生的新产品的偏号，M代表方蜜所需原产品个数，按下来的 M个整数代表了该方窗所需的每个原产品的个数。 |输出描述 根据目前的分额和给出的方案，经过若干次转换，输出当前用户能够得到产品N的份额最大值. 使用golang
某公司目前推出了N个在售的金融产品（1<N≤100），对于张三，我们用a,表示他购买了a；（0≤a<104）单位份额的第价个产品(1≤14N），现给出K（1<K<N）个方蜜，通过这些方室，能够支持将多个不同的产品进行整合（也可以对单个产品进行优化）形成新的产品，新的产品形成后，然用户持有了组成新产品所需的全部的原产品份额，则能够将用户持有的原产品份额转换为新产品的份额，各顺产届份额与新产品份额比例均为1:1。 我们保证，对于德个产品最多存在一个方窑使用旧产品整合成该产品，并且根据方案产出的新产品的产品编号均大于各旧产品的产品病写，现就划根据这些方基，帮助部分原升级到绿新产品的用户对产品进行升级。清协助工作人员计算当前用户能够转深出的最新产品的期的最大值.|输入描述 第一行包含整数N.第二行包含N个整数ai。第三行包含整数K。 接下来的K行，每一行代表一个方案，每一行包含整数L和M(M>1），L为该方窒产生的新产品的偏号，M代表方蜜所需原产品个数，按下来的 M个整数代表了该方窗所需的每个原产品的个数。 |输出描述 根据目前的分额和给出的方案，经过若干次转换，输出当前用户能够得到产品N的份额最大值. 使用golang
暴力搜索可解决此问题，但时间复杂度较高。可以使用动态规划来优化求解过程。
定义一个二维数组dp[i][j]表示用户持有前i个产品，能够转换成产品j的最大份额。则有以下状态转移方程：
1.当第i个产品不参与转换时，dp[i][j]=dp[i-1][j]。
2.当第i个产品参与转换时，dp[i][j]=max(dp[i][j], dp[i-1][k]+min(a[i],需要的产品i的份额)/需要的产品i的份额*转换后产品j的份额)。
其中k表示第i个产品之前的产品，min(a[i],需要的产品i的份额)/需要的产品i的份额表示用户持有的第i个产品能够参与的最大转换次数，转换后的新产品份额为1:1，即与需要的产品i的份额相同。
最终结果为dp[N][N]，表示用户持有前N个产品能够转换成产品N的最大份额。
时间复杂度为O(N^3)，可以通过本题。以下为AC代码：