AdditionalFile4998.zip

#4998. 「POI 2023/2024 R3」Bukmacher

标签: 传统 | 时间限制: 10000 ms | 内存限制: 512 MiB |

题目描述

题目译自 XXXI Olimpiada Informatyczna – III etap Bukmacher

Bajtocja 正饱受通货膨胀困扰，忧心忡忡的 Bajtazar 苦思如何保值资产。不幸的是，他被一则博彩广告吸引，决定投身赌注，押注足球比赛。

即将举行 $n$ 场足球比赛，每场必有胜负（无平局）。单个赌注需预测全部 $n$ 场比赛结果。若正确预测第 $i$ 场比赛，胜方为第一队则获利 $a_i$ 拜托拉，第二队则获利 $b_i$ 拜托拉。错误预测无收益。赌注总收益为所有正确预测的收益之和。

Bajtazar 需从 $z$ 个赌注中选择一个。第 $i$ 个赌注包含预测序列 $p_i$（长度 $n$）和价格 $k_i$ 拜托拉，其中 $p_{i,j}$ 为 $0$ 表示第 $j$ 场比赛预测第一队胜，为 $1$ 表示第二队胜。赌注净收益为总收益减去价格。

Bajtazar 向你提供了所有赌注信息，并提出 $q$ 个问题。第 $i$ 个问题给出一个比赛结果序列 $w_i$，其中 $w_{i,j}$ 为 $0$ 表示第 $j$ 场比赛第一队胜，为 $1$ 表示第二队胜。你的任务是计算在 $w_i$ 结果下，选择任一赌注可获得的最大净收益，以及达成此收益的赌注数量。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 20)$，表示比赛场数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(0 \leq a_i \leq 10^9)$，表示第一队胜的收益。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$ $(0 \leq b_i \leq 10^9)$，表示第二队胜的收益。

第四行包含一个整数 $z$ $(1 \leq z \leq 10^6)$，表示赌注数量。

接下来的 $z$ 行，每行描述第 $i$ 个赌注：一个长度 $n$ 的 $01$ 序列 $p_i$（无空格），后跟整数 $k_i$ $(0 \leq k_i \leq 10^9)$。

下一行包含一个整数 $q$ $(1 \leq q \leq 10^6)$，表示问题数量。

接下来的 $q$ 行，每行包含一个长度 $n$ 的 $0$ 或 $1$ 序列 $w_i$（无空格），描述第 $i$ 个问题的比赛结果。

输出格式

输出 $q$ 行，第 $i$ 行包含两个整数：第一个为在 $w_i$ 结果下任一赌注可获得的最大净收益，第二个为达成此收益的赌注数量。

样例

输入

3
1 3 5
4 2 5
5
000 5
010 2
101 1
000 8
011 3
3
000
011

输出

4 2
5 1
6 1

给定 $a_1=1, a_2=3, a_3=5$，$b_1=4, b_2=2, b_3=5$，赌注预测序列为 $p_1=000, p_2=010, p_3=101, p_4=000, p_5=011$，价格为 $k_1=5, k_2=2, k_3=1, k_4=8, k_5=3$。

• 问题 $1$：$w_1=000$，各赌注净收益：
  • 赌注 $1$：$a_1 + a_2 + a_3 - k_1 = 4$
  • 赌注 $2$：$a_1 + a_3 - k_2 = 4$
  • 赌注 $3$：$a_2 - k_3 = 2$
  • 赌注 $4$：$a_1 + a_2 + a_3 - k_4 = 1$
  • 赌注 $5$：$a_1 - k_5 = -2$
    最大净收益 $4$，由赌注 $1$ 和 $2$ 达成，数量为 $2$。
• 问题 $2$：$w_2=011$，赌注 $5$ 净收益 $a_1 + b_2 + b_3 - k_5 = 5$ 为最大，数量为 $1$。
• 问题 $3$：$w_3=100$，赌注 $3$ 净收益 $b_1 + a_2 - k_3 = 6$ 为最大，数量为 $1$。

附加样例

1. $n=20, a_i=1, b_i=2, z=q=1000, k_i=i$，$p_i$ 和 $w_i$ 为从 $00\ldots0$ 开始的字典序序列。
2. $n=10, a_i=b_i=i, z=q=10^6, k_i=23$，$p_i$ 和 $w_i$ 为从 $00\ldots0$ 开始的循环字典序序列。
3. $n=17, a_i=b_i=10^9, z=q=10^5, k_i=0$，$p_i$ 和 $w_i$ 为从 $11\ldots1$ 开始的递减字典序序列。
4. $n=20, a_i=b_i=i-1, z=q=10^6, k_i=10^9-i$，$p_i$ 和 $w_i$ 为从 $00\ldots0$ 开始的字典序序列。

数据范围与提示

详细子任务附加限制及分值如下表所示。

若程序仅正确输出每对结果的第一个值（最大净收益），且第二个值在 32 位有符号整数范围内（int），可获测试 $50\%$ 分数。