TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2974
  • Problem
  • P2974射箭
    Limits : Time Limit : 10000 MS   Memory Limit : 165536 KB
    Description

       何老板是一名箭术爱好者,今天他又到箭馆里去玩射箭游戏。
       游戏中会出现m(编号1到m)只怪兽,怪兽按编号1到m依次出现。每个怪兽的颜色和价值可能不同。若当前出现的是一只颜色为x的怪兽,何老板须用一只颜色同为x的箭才能杀死这只怪兽。
       游戏中,何老板有n(编号1到n)只箭,每只箭的颜色可能不同。游戏规定必须从第1号箭开始,用一段连续编号的箭去射杀连续一段怪兽,若遇到某只怪兽无法被杀死,游戏结束(当然,箭用完了或者没有怪兽可杀了,游戏也会结束)。
       也就是说,一开始只能射1号箭。若选1号箭射y号怪兽,那么只能用2号箭射y+1号怪兽,3号箭射y+2号怪兽......,若第k号箭无法杀死第y+k-1号怪兽,游戏结束,该局游戏得分为k-1。
       每秒钟会有一只怪兽出现在屏幕上,一秒钟以后该怪兽会消失,不会再出现了。何老板一秒钟可以射出一支箭,且百发百中,现在已知每个怪兽的颜色和价值,问何老板最多能得多少分。输出最高得分的方案和该方案杀死的怪兽的总价值,若有多种方案,输出总价值最大的那种(在得分最高的前提下,要求总价最高)。

    Input Format

    第一行,两个整数n和m,1<=n<=m<=20000
    第二行,n个大写字母,表示编号1到n的箭的颜色。
    第三行,m个大写字母,表示编号1到m的怪兽的颜色。
    第四喊,m个空格间隔的整数,表示编号1到m的怪兽的价值。

    Output Format

    一行,两个空格间隔的整数,分别表示最大得分和最大总价值。

    Sample Input 1

    4 8
    ABCD
    ABCEDABC
    1 6 3 5 1 4 2 9 

    Sample Output 1

    3 15

    Sample Input 2

    7 15
    ZPFHOOX
    ZPFZPFHOOZPFHOO
    729 221 256 196 557 234 232 460 546 645 107 972 421 783 246 

    Sample Output 2

    6 3174

    Sample Input 3

    10 22
    TEBZLVRQDN
    TEBZLVTEBZLVRQTEBZLVRQ
    275 276 305 467 698 612 599 429 500 996 843 61 651 335 860 565 544 968 919 90 718 136 

    Sample Output 3

    8 4800

    Hint

    数据范围:
    50% 1<=n<=m<=200
    100% 1<=n<=m<=20000
    0<=怪兽的价值<=1000

    样例1说明:
    用编号1、2、3这连续三只箭射杀1、2、3号或者6、7、8号怪兽
    杀死6、7、8三只,价值为4+2+9