# The Traveler's Journey
## Problem Statement
You are given $N$ cities arranged linearly on a number line, indexed from $1$ to $N$. Your objective is to travel from city $1$ to city $N$ with the minimum possible cost.
You have two modes of transportation available from any city $i$:
1. **Bus:** You can travel from city $i$ to the adjacent city $i+1$.
* The cost to move from city $i$ to city $i+1$ is given by $B_i$.
2. **Airplane:** You can fly from city $i$ to any city $i+j$, provided that the jump length $j$ is within the range $[1, K]$ (i.e., you can fly to any city from $i+1$ to $i+K$, inclusive).
* The cost to fly from city $i$ to city $i+j$ is calculated as $A_i + A_{i+j}$. This represents the cost associated with the departure airport at city $i$ plus the cost associated with the arrival airport at city $i+j$.
Find the minimum cost required to travel from city $1$ to city $N$.
## Input Format
The first line contains two integers: $n$, $k$.
* $n$ ($1 \le n \le 10^5$) - the number of cities.
* $k$ ($1 \le k \le n$) - the maximum flight distance.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) - where $a_i$ is the airport cost factor for city $i$.
The third line contains $n-1$ integers $b_1, b_2, \dots, b_{n-1}$ ($1 \le b_i \le 10^9$) - where $b_i$ is the cost to take the bus from city $i$ to city $i+1$.
## Output Format
Print a single integer representing the minimum cost to reach city $N$.
## Sample Test Cases
### Sample Input 1
```
4 2
10 20 10 50
5 10 100
```
### Sample Output 1
```
75
```
## Constraints
* $1 \le n \le 10^5$
* $1 \le k \le n$
* $1 \le a_i \le 10^9$ for $1 \le i \le n$
* $1 \le b_i \le 10^9$ for $1 \le i \le n-1$
* Time limit: 1 second
* Memory limit: 256 MB
## Explanation
For Sample Input 1:
We have $N=4$ cities and a maximum flight jump $K=2$.
* Airport costs $A = [10, 20, 10, 50]$ (for cities $1, 2, 3, 4$ respectively).
* Bus costs $B = [5, 10, 100]$ (for segments $1\to2, 2\to3, 3\to4$ respectively).
Let's analyze possible paths from city $1$ to city $4$:
1. **Bus Only:** $1 \to 2 \to 3 \to 4$
* Cost: $B_1 + B_2 + B_3 = 5 + 10 + 100 = 115$.
2. **Fly $1 \to 3$, then Bus $3 \to 4$:** (Flight $1 \to 3$ is valid as $3-1=2 \le K$)
* Flight $1 \to 3$ cost: $A_1 + A_3 = 10 + 10 = 20$.
* Bus $3 \to 4$ cost: $B_3 = 100$.
* Total: $20 + 100 = 120$.
3. **Bus $1 \to 2$, then Fly $2 \to 4$:** (Flight $2 \to 4$ is valid as $4-2=2 \le K$)
* Bus $1 \to 2$ cost: $B_1 = 5$.
* Flight $2 \to 4$ cost: $A_2 + A_4 = 20 + 50 = 70$.
* Total: $5 + 70 = 75$.
The minimum cost among these paths is $75$.
Loading problem statement...