题目描述

　平平带着韵韵来到了游乐园，看到了n 辆漂亮的遥控车，每辆车上都有一个唯一的名字name[i]。韵韵早就迫不及待地想玩名字是s 的遥控车。可是韵韵毕竟还小，她想象的名字可能是一辆车名字的前缀（也就是说能确定一个i，使s 是name[i]的前缀），这时她就能玩第i 辆车；或者是一个无中生有的名字，即s 不是任何一辆车名字的前缀，这时候她什么也不能玩。
　　你需要完成下面的任务：
　　1.韵韵想了m 个她想要的名字，请告诉她能玩多少次。
　　2.由于管理员粗心的操作，导致每辆车的摆放位置都可能出现微小的差错，原来第i 辆车现在的位置可能是i-1、i、i+1 中的任意一个（第1 辆车的位置不可能是0，第n辆车的位置不可能是n+1）。请你计算出共有多少种可能的排列。
　　注：数据保证当s 是name[i]的前缀时，i 是唯一确定的。一辆车可以玩多次。

输入

　第一行是2 个正整数n、m。
　　接下来n 行，每行1 个字符串name[i]，表示第i 辆车的名字。接下来m 行，每行1 个字符串s，表示韵韵想要的名字。

输出

第一行输出韵韵能玩的次数。第二行输出共有多少种可能的排列。

思路

前一个问题很简单，就是字符串的简单运用，后一问是n-1的高精度斐波那契数列，
所以这题就很简单了，但要注意时间如果直接进行字符操作的话会超时，所以我们可以根据字符串的长度进行一次排序，如果想要的名字长度比车的名字长度要大的话就可以直接结束了

var
 a,b:Array [0..100001,1..10] of longint;
 f:array [0..100020] of longint;
 num:array [1..10] of longint;
 n,i,j,time,x:longint;

procedure qsort<span class="hljs-params">(l,r,x:longint);
 vari,j,mid,temp:longint;
begin
 ifl>=r then exit;
 mid:=a[l+random(r-l+1),x];
 i:=l; j:=r;
 repeat
 while a[i,x]>mid do inc(i);
 while a[j,x]<mid do dec(j);
  ifi<=j then
  begin
   temp:=a[i,x]; a[i,x]:=a[j,x]; a[j,x]:=temp;
   inc(i); dec(j);
  end;
 until i>j;
 qsort(l,j,x);
 qsort(i,r,x);
end;

begin
 readln(n,time);
 fori:=1 to n do
 begin
  read(x);
  inc(num[x]);
  read(a[num[x],x]);
 end;
 fori:=1 to 10 do
 qsort(1,num[i],i);
 fori:=0 to time do
 begin
  for j:=1 to 10 do
   begin if b[i,j]<num[j] then
    begin
     if f[i+j]<f[i]+a[b[i,j]+1,j] then
      begin
       f[i+j]:=f[i]+a[b[i,j]+1,j];
       b[i+j]:=b[i];
       b[i+j,j]:=b[i,j]+1;
      end;
    end;
   end;
 end;
 write(f[time]);
end.