Bài. Dãy con chung dài nhất có trọng số

Mô tả

Cho hai xâu A, B chỉ gồm chữ cái thường.
Mỗi ký tự có trọng số bằng vị trí của nó trong bảng chữ cái:

• a = 1, b = 2, ..., z = 26.

Hãy tìm tổng trọng số lớn nhất của một dãy con chung của hai xâu.

Input

• Dòng 1 chứa xâu A.
• Dòng 2 chứa xâu B.

Output

• In ra tổng trọng số lớn nhất có thể đạt được.

Ràng buộc

• 1 <= |A|, |B| <= 1000

Subtask

• Subtask 1 (30%): |A|, |B| <= 100
• Subtask 2 (70%): Không có ràng buộc gì thêm.

Ví dụ

Input

abca
cada

Output

5

Giải thích ví dụ

Một dãy con chung tối ưu là aca, có tổng trọng số 1 + 3 + 1 = 5.