Alice đang phải giải quyết bài toán xử lý chuỗi sinh học như sau:

• Một chuỗi kí tự đầu vào \(S\) mô tả một đoạn dữ liệu ADN. Trong bài toán này, Alice đã đánh thứ tự các kí tự của chuỗi bắt đầu từ \(0\) và sử dụng tất cả các kí tự in thường để mô tả dữ liệu.
• Một tập hợp gồm \(n\) mẫu chuỗi \(\{w_1, w_2, \dots, w_n\}\), mẫu \(w_i\) (\(1 \le i \le n\)) có trọng số \(p_i\) phản ánh mức độ hữu ích của mẫu đó trong khai thác dữ liệu.

Mỗi khi một mẫu \(w_i\) xuất hiện như một chuỗi con liên tiếp trong \(S\), Alice có thể thực hiện một thao tác trích xuất: xóa bỏ đoạn tương ứng là mẫu khỏi chuỗi, dồn phần còn lại liền nhau và thu được một lợi ích có giá trị bằng \(p_i\). Quá trình này có thể lặp lại cho đến khi không tìm được mẫu nào xuất hiện trong chuỗi hiện tại.

Yêu cầu

• Hãy xác định chiến lược trích xuất mẫu sao cho tổng lợi ích thu được là lớn nhất, sau khi không còn có thể trích xuất thêm mẫu nào từ chuỗi.

Input

• Dòng đầu là xâu \(S\) ban đầu (độ dài không quá \(1000\), chỉ gồm các kí tự 'a' đến 'z').
• Dòng thứ hai là số \(n\) (\(n \le 3000\)).
• \(n\) dòng sau, mỗi dòng mô tả mẫu chuỗi thứ \(i\) gồm: \(w_i\) (độ dài không quá \(30\) và chỉ gồm các kí tự 'a' đến 'z'), \(p_i\) (\(0 < p_i \le 10^4\)).

Output

• Dòng thứ nhất chứa một số nguyên \(k\) là số thao tác trích xuất.
• Tiếp theo là \(k\) dòng, mỗi dòng chứa hai số \(L, R\) cho biết thao tác trích xuất tương ứng sẽ xóa toàn bộ các kí tự từ vị trí \(L\) đến vị trí \(R\) (vị trí tính từ \(0\) trên chuỗi tại thời điểm thực hiện thao tác đó).

Example

abcbca
3
bc 10
abc 15
a 5

3
0 2
0 1
0 0