Bessie rất thích xem các chương trình được chiếu trên Mooloo. Bởi vì Bessie là một cô bò bận rộn, cô ấy đã lên lịch cho \(N\) \((1 \le N \le 10^5)\) ngày xem Mooloo của mình. Do Mooloo là một dịch vụ trả tiền định kì, Bessie cần tối thiểu hoá số tiền mà cô ấy cần phải trả.

Mooloo có một cách đăng kí dịch vụ rất thú vị: bạn cần tốn \(d + K\) \((1 \le K \le 10^9)\) đồng moonies để sử dụng dịch vụ trong \(d\) ngày liên tiếp, bạn hoàn toàn có thể đăng kí tại bất cứ thời điểm nào, và có thể đăng kí gói mới không giới hạn số lần nếu như gói dịch vụ hiện tại đã hết hạn. Hãy cho Bessie biết số tiền ít nhất cần dành ra nhé!

Input

• Dòng đầu tiên là hai số \(N\) và \(K\).
• Dòng thứ hai là \(N\) ngày \(d_i\) \((1 \le i \le N)\) mà Bessie sẽ xem Mooloo, thoả mãn: \(1 < d_1 < d_2 < ... < d_N \le 10^{14}\).

Output

• Số tiền mà Bessie cần trả.

Scoring

• Subtask \(1\): \(N \le 10\).
• Subtask \(2\): Không có ràng buộc gì thêm.

2 4
7 9

7

2 3
1 10

8

Tranh khắc dấu là một bức tranh đen trắng trên một tấm vải có kích thước \(N \times N\), trong đó một số ô được tô mực và số còn lại được để trống. Nó có thể được biểu diễn bằng một mảng \(N \times N\) (\(1 \le N \le 20\)). Phần tử thứ \(i\) của cột thứ \(j\) trong mảng là * nếu ô đó được tô và . nếu để trống.

Bessie muốn làm một bức tranh khắc dấu, vì vậy bác John đã cho cô mượn một con dấu có kích thước \(K \times K\) (\(1 \le K \le N\)) và một tấm vải \(N \times N\). Bessie có thể xoay con dấu theo chiều kim đồng hồ \(90^o\) và đóng dấu ở bất kỳ đâu trên tấm vải miễn là con dấu nằm hoàn toàn trong tấm vải. Cụ thể, để đóng dấu, Bessie chọn các số nguyên \(i, j\) sao cho \(i \in [1, N-K+1]\) và \(j \in [1, N-K+1]\); với mỗi \((i', j')\) sao cho \(1 \le i', j' \le K\), ô vải \((i+i'-1, j+j'-1)\) được tô đen nếu con dấu có mực tại \((i', j')\). Bessie có thể xoay con dấu bất kỳ lúc nào giữa các lần đóng dấu. Nếu một ô đã được tô, nó sẽ giữ nguyên màu.

Bác John muốn biết liệu Bessie có thể tạo ra tranh tem mong muốn của mình với con dấu của ông hay không. Với \(T\) (\(1 \le T \le 100\)) bộ test, hãy giúp bác John trả lời câu hỏi này.

INPUT

Nhập dữ liệu từ terminal / stdin:

• Dòng đầu tiên chứa số nguyên \(T\), số lượng bộ test \((1 \le T \le 100)\).
• Mỗi bộ test bao gồm:
  • Một số nguyên \(N\), sau đó là \(N\) dòng, mỗi dòng chứa một chuỗi ký tự * và ., mô tả bức tranh mong muốn.
  • Một số nguyên \(K\), sau đó là \(K\) dòng, mỗi dòng chứa một chuỗi ký tự * và ., mô tả con dấu.

Note: Các truy vấn được phân cách bởi một dòng trống.

OUTPUT

In ra terminal/stdout:

• Với mỗi bộ test, in "YES" nếu có thể tạo ra bức tranh mong muốn, ngược lại in "NO".

SCORING

• \(100\%\) subtasks không có ràng buộc nào khác

4

2
**
*.
1
*

3
.**
.**
***
2
.*
**

3
...
.*.
...
3
.*.
...
...

3
**.
.**
..*
2
.*
*.

YES
YES
NO
YES

Bessie là một cô bò rất hay đói bụng. Mỗi ngày, vào giờ ăn tối, nếu có cỏ khô trong chuồng, nó sẽ ăn một bó. Để Bessie không bị đói, bác nông dân John thỉnh thoảng sẽ mang cỏ khô đến vào buổi sáng (trước bữa tối). Cụ thể, vào ngày \(dᵢ\), bác John gửi \(b_i\) kiện cỏ khô \((1 \le d_i \le 10^{14}, 1 \le b_i \le 10^9)\).

Tính tổng số bó cỏ khô mà Bessie sẽ ăn trong \(T\) ngày đầu tiên.

INPUT

Nhập dữ liệu từ terminal/stdin:

• Dòng đầu tiên chứa \(N\) và \(T\) \((1 \le N \le 10^5, 1 \le T \le 10^{14})\).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(d_i\) và \(b_i\). Đảm bảo rằng 1 < \(d_1\) < \(d_2\) < ... < \(d_n\) ≤ \(T\).

OUTPUT

In ra terminal/stdout:

• In ra số lượng kiện cỏ khô mà Bessie sẽ ăn trong \(T\) ngày đầu tiên.

Note: Vì các số trong bài toán có thể rất lớn, bạn nên sử dụng kiểu dữ liệu số nguyên 64 bit (ví dụ: long long trong C/C++).

SCORING

• Input \(4 - 7\): \(T \le 10^5\)
• Input \(8 - 13\): Không có ràng buộc gì thêm

1 5
1 2

2

2 5
1 2
5 10

3

2 5
1 10
5 10

5