对于一个长度为n的字符串S,我们称字符串为字符串的一个前缀,称字符串为字符串的一个后缀。 我们称两个字符串是相似的,当且仅当它们的成分相同,并且组成各成分出现的数目相同。例如字符串"abbcdf"与字符串"bcfdab"就是相似的,而"abbcdf"与"abcdf"不相似,因为它们虽然成分相同,但是各成分出现的次数不同。 牛牛本来有两个长度均为n的01字符串s,t,但是t串由于数据损坏,导致一些位置不确定到底是0还是1,不过好在,牛牛清楚的记得t串中有个0与个1。 接下来牛牛要还原损坏的t串。 s串和t串每有一个非空前缀相似,就得到的得分,(不一定是一个正数,当它的值为负时表示失去的得分) s串和t串每有一个非空后缀相似,就得到的得分,(不一定是一个正数,当它的值为负时表示失去的得分) 牛牛想要知道它能够还原的t串中的最小得分与最大得分。
输入描述:
第一行输入五个整数n,,,, 。且保证接下来输入两行表示字符串s,t,s=t=n其中,s串完全由'0','1'组成,t串完全由'0','1','?'组成。?表示损坏的部分,也就是需要你还原的部分。输入数据保证t串中0的数目,1的数目,也就是至少存在一种合法填充t串中?的方案。


输出描述:
请输出两个整数,表示还原后的最小得分与最高得分。
示例1

输入

8 6 2 1 1
10110011
????????

输出

0 4

说明

可以构造01串t="00011000"达到最小得分(与s串没有相似的前缀与后缀)

可以构造01串t="00000011"(4个相似的后缀)达到最大得分。

示例2

输入

20 1 19 55 97
11111010101111111111
1?????1?1?1????????1

输出

566 1439

说明

最小:"11111111111111111101"
最大:"11111111101111111111"
示例3

输入

1 0 1 -999 1000
0
?

输出

0 0

说明

因为限制条件为必须有1个1,所以?处只能填1
加载中...