Bài tập

Cho hai xâu ký tự \(A\) và \(B\). Trên xâu \(A\) được phép thực hiện các phép biến đổi sau, mỗi phép tính là một thao tác:

• Xoá một ký tự bất kỳ của \(A\);
• Chèn một ký tự bất kỳ vào một vị trí bất kỳ của \(A\);
• Thay một ký tự của \(A\) bằng một ký tự khác.

Hãy tính số thao tác ít nhất để biến \(A\) thành \(B\).

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ test.
• Mỗi bộ test gồm hai dòng: dòng đầu là xâu \(A\), dòng thứ hai là xâu \(B\).

Output

Với mỗi bộ test in ra một dòng là số thao tác tối thiểu.

Constraints

• \(1 \le T \le 10\)
• Mỗi xâu chỉ gồm chữ cái in hoa, độ dài từ \(1\) đến \(2000\).

Sample Input

3
KITTEN
SITTING
ABC
ABC
AAAA
B

Sample Output

3
0
4

Explanation

KITTEN \(\to\) SITTEN (thay K bằng S) \(\to\) SITTIN (thay E bằng I) \(\to\) SITTING (chèn G): 3 thao tác. Bộ test thứ hai hai xâu giống nhau. Bộ test thứ ba: giữ lại một chữ A, thay bằng B rồi xoá 3 chữ còn lại, tổng 4 thao tác.

Hai chú kangaroo đứng trên một đường thẳng và nhảy cùng chiều (về phía số lớn hơn), các lần nhảy của hai chú diễn ra đồng thời.

• Chú thứ nhất xuất phát ở vị trí \(x_1\), mỗi lần nhảy tiến thêm \(v_1\).
• Chú thứ hai xuất phát ở vị trí \(x_2\), mỗi lần nhảy tiến thêm \(v_2\).

Hỏi có tồn tại một số lần nhảy \(t \ge 0\) (sau đúng \(t\) lần nhảy của mỗi chú) mà hai chú đứng cùng một vị trí hay không? In YES nếu có, ngược lại in NO.

Input

Một dòng gồm bốn số nguyên \(x_1, v_1, x_2, v_2\).

Output

In YES hoặc NO.

Constraints

• \(0 \le x_1 \le x_2 \le 10000\).
• \(1 \le v_1, v_2 \le 10000\).

Sample Input

2 5 11 2

Sample Output

YES

Explanation

Sau \(3\) lần nhảy: chú thứ nhất ở \(2 + 3 \cdot 5 = 17\), chú thứ hai ở \(11 + 3 \cdot 2 = 17\).

Cho một xâu ký tự \(S\) đã được chuẩn hóa: chỉ gồm các chữ cái tiếng Anh viết thường và dấu cách; giữa hai từ liên tiếp có đúng một dấu cách; không có dấu cách ở đầu và cuối xâu.

Hãy biến đổi xâu bằng cách viết hoa chữ cái đầu tiên của mỗi từ (các chữ cái còn lại giữ nguyên) rồi in kết quả.

Gợi ý: xây dựng hàm \(HoadauTu(S)\) thực hiện việc này.

Input

• Một dòng duy nhất chứa xâu \(S\).

Output

• In ra xâu \(S\) sau khi viết hoa chữ cái đầu mỗi từ.

Constraints

• \(1 \le |S| \le 10^6\)

Sample Input 1

nguyen van an

Sample Output 1

Nguyen Van An

Sample Input 2

hanoi

Sample Output 2

Hanoi

Do dịch cúm gia cầm, một hộ nông dân phải tiêu hủy \(n\) con gia cầm và được nhà nước hỗ trợ tiền theo độ tuổi của từng con:

• Loại 1 (dưới một tháng tuổi): \(a\) đồng mỗi con;
• Loại 2 (từ một tháng đến dưới ba tháng tuổi): \(b\) đồng mỗi con;
• Loại 3 (từ ba tháng tuổi trở lên): \(c\) đồng mỗi con.

Trong số \(n\) con bị tiêu hủy có \(m\) con loại 1, \(k\) con loại 2, số còn lại thuộc loại 3. Hãy tính tổng số tiền hộ nông dân được hỗ trợ.

Input

• Một dòng gồm sáu số nguyên \(a, b, c, m, n, k\) theo đúng thứ tự này, cách nhau bởi dấu cách.

Output

• In ra tổng số tiền hỗ trợ.

Constraints

• \(1 \le a, b, c, m, n, k \le 100000\)
• \(m + k \le n\)

Sample Input 1

7 4 2 3 8 3

Sample Output 1

37

Explanation

Có \(3\) con loại 1, \(3\) con loại 2 và \(8 - 3 - 3 = 2\) con loại 3, nên tổng tiền là \(3 \cdot 7 + 3 \cdot 4 + 2 \cdot 2 = 37\).