시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 0 0 0 0.000%

문제

เครื่องดนตรีกระต่ายถูกสร้างขึ้นด้วยความอัจฉริยะของคนสมัยก่อนประวัติศาสตร์เพื่อสร้างความ บรรเทิงให้กับกระต่าย โดยเครื่องดนตรีนี้จะมีตัวโน๊ตทั้งหมด 26 ตัว เขียนแทนด้วยตัวอักษรภาษาอังกฤษ ตัวพิมพ์ใหญ่ A ถึง Z เมื่อน าตัวอักษรเหล่านี้มาเรียงต่อกันก็จะได้เป็นบทเพลงกระต่าย โดยตัวอักษร 1 ตัว หมายถึงการเล่นโน๊ตนั้น 1 จังหวะ ความยาวของบทเพลงนับจากจ านวนตัวอักษร เช่น AASDFG เป็นเพลงที่มี ความยาว 6 โดยจังหวะที่ 1 เล่นตัวโน๊ต A, จังหวะที่ 2 เล่นตัวโน๊ต A, จังหวะที่ 3 เล่นตัวโน๊ต S, จังหวะที่ 4 เล่นตัวโน๊ต D, จังหวะที่ 5 เล่นตัวโน๊ต F และจังหวะที่ 6 เล่นตัวโน๊ต G เป็นต้น

เมื่อไม่นานมานี้นักจิตวิทยากระต่ายได้ค้นพบว่าตัวโน๊ตจังหวะที่ i+1 จะให้ค่าความสุขขึ้นอยู่กับรูปแบบ ตัวโน๊ตจังหวะที่ i และ i+1 ตาม “ตารางค่าความสุขจากตัวโน๊ต” ซึ่งกระต่ายแต่ละตัวจะมีตารางนี้ไม่เหมือนกัน ตัวโน๊ตจังหวะที่ 1 ไม่ให้ค่าความสุขใดๆ

ตัวอย่าง"ตารางค่าความสุขจากตัวโน๊ต"

  โน๊ตจังหวะที่ i+1
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
โน๊ตจังหวะที่ i
A 9 9 8 7 7 0 3 1 6 2 9 7 0 0 0 5 3 2 6 5 4 1 4 7 8 0
B 6 2 9 5 0 4 8 3 8 2 8 1 9 7 0 6 3 0 2 1 0 5 0 7 9 3
C 9 7 5 9 9 6 2 1 5 6 3 7 9 1 8 8 7 0 8 1 8 8 1 0 1 8
D 1 6 9 1 5 0 7 8 0 2 0 9 8 0 2 0 0 1 8 8 4 8 6 3 4 2
E 4 6 0 5 6 5 9 7 7 1 8 4 6 3 2 3 8 3 2 4 8 8 0 2 4 3
F 2 8 9 4 8 0 9 5 4 2 7 9 3 4 3 7 5 5 1 5 2 4 0 6 1 1
G 0 2 8 7 6 9 6 5 8 0 7 6 8 6 1 7 3 0 3 5 9 0 6 5 0 7
H 5 6 6 2 8 8 6 7 4 6 0 2 8 2 5 3 4 9 6 2 1 8 7 4 4 9
I 1 3 0 1 8 2 2 2 5 1 4 3 6 9 4 9 0 3 0 2 1 5 2 5 5 8
J 5 2 5 0 3 2 0 0 9 7 4 0 8 5 6 0 2 6 9 0 0 6 0 2 8 7
K 7 2 8 7 8 4 5 0 9 4 0 2 6 3 6 0 2 7 3 9 9 4 8 7 7 9
L 6 9 7 2 0 8 3 4 2 9 3 4 1 8 7 1 1 3 4 1 3 9 0 6 4 9
M 9 6 7 6 1 7 1 7 2 2 5 0 4 8 5 6 8 0 4 0 0 1 6 8 4 5
N 1 0 7 6 9 0 3 6 2 5 0 4 2 8 3 6 4 3 0 9 3 4 2 9 8 5
O 0 4 9 9 3 2 1 6 6 9 2 4 9 6 1 2 5 6 0 8 4 2 0 3 6 9
P 6 9 8 5 3 9 9 0 7 1 8 8 1 9 4 0 2 9 1 3 1 4 0 7 3 8
Q 0 7 4 9 3 4 5 4 1 9 7 1 7 2 6 4 1 7 7 2 5 6 0 9 2 9
R 0 9 4 9 5 0 1 7 7 7 8 7 0 6 9 6 8 6 7 5 3 1 7 9 7 0
S 0 6 1 2 7 2 6 7 3 7 6 2 7 5 3 3 2 1 0 3 2 6 2 8 6 8
T 6 1 8 1 4 0 5 6 5 8 1 0 6 5 8 9 1 4 8 6 3 4 5 1 2 4
U 4 9 9 5 4 3 8 6 0 6 1 0 4 7 4 5 4 9 8 3 0 5 2 7 6 0
V 2 4 2 1 7 1 3 9 4 7 0 5 5 1 9 1 3 0 4 3 4 3 2 8 9 3
W 8 9 9 1 6 3 5 9 4 9 3 7 3 8 0 4 1 0 9 0 0 5 5 8 3 6
X 8 5 8 6 8 5 4 1 1 0 4 0 8 6 7 7 1 7 9 9 6 6 7 5 5 2
Y 3 0 0 0 7 5 5 4 0 3 2 0 9 6 6 1 4 2 4 5 3 6 2 7 9 7
Z 9 0 1 6 1 1 7 8 1 0 1 6 1 5 2 6 8 1 3 3 0 6 6 4 2 4

จากตารางข้างต้นสามารถค านวนค่าความสุขที่ได้จากบทเพลง AASDFG ได้ดังนี้ จังหวะที่ 1 ให้ค่า ความสุข 0, จังหวะที่ 2 ให้ค่าความสุข 9, จังหวะที่ 3 ให้ค่าความสุข 6, จังหวะที่ 4 ให้ค่าความสุข 2, จังหวะที่ 5 ให้ค่าความสุข 0 และจังหวะที่ 6 ให้ค่าความสุข 9 ดังนั้นเพลง AASDFG ให้ค่าความสุข 0+9+6+2+0+9 = 26 หน่วย

เรามี“ตารางค่าความสุขจากตัวโน๊ต” อยู่แล้ว อยากให้คุณช่วยเขียนโปรแกรมหาค่าความสุขที่มาก ที่สุดที่ได้จากบทเพลงที่มีตัวโน๊ตตัวแรกและมีความยาวตามที่เราก าหนด

입력

บรรทัดแรกเป็นจ านวนกรณีทดสอบ T ชุด (1 ≤ T ≤ 10) กรณีทดสอบแต่ละชุดประกอบด้วยข้อมูลดังนี้

  1. “ตารางค่าความสุขจากตัวโน๊ต” จ านวน 26 บรรทัด แต่ละบรรทัดมีค่าความสุข sij จ านวน 26 ค่า แต่ละค่าคั่นด้วยช่องว่าง ค่าเหล่านี้เรียงล าดับเช่นเดียวกับตัวอย่าง “ตารางค่าความสุขจาก ตัวโน๊ต” (0 ≤ sij ≤ 100)
  2. บรรทัดถัดมาเป็นจ านวนค าถาม N ค าถาม (1 ≤ N ≤ 10)
  3. ถัดมา N บรรทัด เป็นตัวอักษรภาษาอังกฤษพิมพ์ใหญ่ C แสดงตัวโน๊ตเริ่มต้นของเพลง และความ ยาวของเพลง L ที่ต้องการ (1 ≤ L ≤ 100 000)

출력

ส าหรับแต่ละกรณีทดสอบให้แสดงจ านวนเต็ม N จ านวน แสดงค่าความสุขที่มากที่สุดของเพลงที่มี ความยาว L จังหวะที่ขึ้นต้นด้วยตัวอักษรที่ก าหนด

예제 입력

1
9 9 8 7 7 0 3 1 6 2 9 7 0 0 0 5 3 2 6 5 4 1 4 7 8 0
6 2 9 5 0 4 8 3 8 2 8 1 9 7 0 6 3 0 2 1 0 5 0 7 9 3
9 7 5 9 9 6 2 1 5 6 3 7 9 1 8 8 7 0 8 1 8 8 1 0 1 8
1 6 9 1 5 0 7 8 0 2 0 9 8 0 2 0 0 1 8 8 4 8 6 3 4 2
4 6 0 5 6 5 9 7 7 1 8 4 6 3 2 3 8 3 2 4 8 8 0 2 4 3
2 8 9 4 8 0 9 5 4 2 7 9 3 4 3 7 5 5 1 5 2 4 0 6 1 1
0 2 8 7 6 9 6 5 8 0 7 6 8 6 1 7 3 0 3 5 9 0 6 5 0 7
5 6 6 2 8 8 6 7 4 6 0 2 8 2 5 3 4 9 6 2 1 8 7 4 4 9
1 3 0 1 8 2 2 2 5 1 4 3 6 9 4 9 0 3 0 2 1 5 2 5 5 8
5 2 5 0 3 2 0 0 9 7 4 0 8 5 6 0 2 6 9 0 0 6 0 2 8 7
7 2 8 7 8 4 5 0 9 4 0 2 6 3 6 0 2 7 3 9 9 4 8 7 7 9
6 9 7 2 0 8 3 4 2 9 3 4 1 8 7 1 1 3 4 1 3 9 0 6 4 9
9 6 7 6 1 7 1 7 2 2 5 0 4 8 5 6 8 0 4 0 0 1 6 8 4 5
1 0 7 6 9 0 3 6 2 5 0 4 2 8 3 6 4 3 0 9 3 4 2 9 8 5
0 4 9 9 3 2 1 6 6 9 2 4 9 6 1 2 5 6 0 8 4 2 0 3 6 9
6 9 8 5 3 9 9 0 7 1 8 8 1 9 4 0 2 9 1 3 1 4 0 7 3 8
0 7 4 9 3 4 5 4 1 9 7 1 7 2 6 4 1 7 7 2 5 6 0 9 2 9
0 9 4 9 5 0 1 7 7 7 8 7 0 6 9 6 8 6 7 5 3 1 7 9 7 0
0 6 1 2 7 2 6 7 3 7 6 2 7 5 3 3 2 1 0 3 2 6 2 8 6 8
6 1 8 1 4 0 5 6 5 8 1 0 6 5 8 9 1 4 8 6 3 4 5 1 2 4
4 9 9 5 4 3 8 6 0 6 1 0 4 7 4 5 4 9 8 3 0 5 2 7 6 0
2 4 2 1 7 1 3 9 4 7 0 5 5 1 9 1 3 0 4 3 4 3 2 8 9 3
8 9 9 1 6 3 5 9 4 9 3 7 3 8 0 4 1 0 9 0 0 5 5 8 3 6
8 5 8 6 8 5 4 1 1 0 4 0 8 6 7 7 1 7 9 9 6 6 7 5 5 2
3 0 0 0 7 5 5 4 0 3 2 0 9 6 6 1 4 2 4 5 3 6 2 7 9 7
9 0 1 6 1 1 7 8 1 0 1 6 1 5 2 6 8 1 3 3 0 6 6 4 2 4
2
A 5
G 10

예제 출력

36
81

힌트