## Đề bài
Trong nhà hàng “Siêu nhân” có hai chú robots hầu bàn rất đắc lực có tên là Cuội và Bờm. Đây là các sản phẩm mới nhất của hãng Cybernetic. Nhiệm vụ của robot là đến bàn có khách hàng và hỏi các thực khách xem họ cần dùng đồ ăn uống gì. Sau khi nhận được đơn đặt hàng của thực khách, robot sẽ gửi thông điệp vào bộ phận nhà bếp để các đầu bếp chuẩn bị các món theo đơn đặt hàng của thực khách, rồi di chuyển đến bàn tiếp theo. Khi đồ ăn uống đã sẵn sàng, chúng sẽ được chuyển theo đường dẫn đặc biệt đến bàn của thực khách.
Cuội và Bờm sẽ chia nhau làm việc, mỗi thực khách sẽ được phục vụ bởi một trong hai robot. Vì hai robot này cũng rất lười di chuyển, nên chúng lên kế hoạch phục vụ rất cẩn thận. Một số thực khách sẽ được phục vụ bởi Bờm, số còn lại được phục vụ bởi Cuội và mục tiêu là tìm cách phân công sao cho tổng độ dài quãng đường phải di chuyển bởi hai robot là nhỏ nhất. Hai robot phải tỏ thái độ lịch sự đối với thực khách, vì thế chúng phục vụ thực khách theo nguyên tắc: Ai đến trước được phục vụ trước. Nghĩa là: nếu thực khách A đến lúc 8:00 còn thực khách B đến lúc 9:00 thì Bờm không được phục vụ thực khách B trước thực khách A. Tuy nhiên, cho phép Cuội phục vụ thực khách B trước, còn Bờm phục vụ thực khách A ở thời điểm muộn hơn:
nghĩa là trình tự trên chỉ cần tuân thủ đối với những thực khách được phục vụ bởi cùng một robot.
**Yêu cầu:** Cho biết vị trí của các thực khách, hãy tìm cách phân công hai robot phục vụ sao cho tổng khoảng cách mà hai robot phải di chuyển là nhỏ nhất.
**Dữ liệu:** Vào từ file văn bản *BCROBOT.INP*:
- Dòng đầu tiên ghi số nguyên n (1 $\leq$ n $\leq$ 500) là số lượng thực khách trong nhà hàng.
- Dòng thứ hai ghi hai số nguyên $x_1, y_1$ (cách nhau bởi dấu cách) là vị trí ban đầu của Cuội.
- Dòng thứ ba ghi hai số nguyên $x_2, y_2$ (cách nhau bởi dấu cách) là vị trí ban đầu của Bờm.
- Dòng thứ i trong số n dòng tiếp theo ghi hai số nguyên x, y là toạ độ của khách hàng thứ i (các khách hàng được liệt kê theo thứ tự mà họ đến nhà hàng).

*Các toạ độ là các số nguyên không âm không vượt quá 2000.*

**Kết quả:** Ghi ra file văn bản *BCROBOT.OUT* một số nguyên là tổng khoảng cách mà hai robot phải di chuyển theo cách phân công tìm được được làm tròn xuống đến số nguyên gần nhất.

## Test ví dụ 1
### input

2 
100 200
200 200
0 200
100 300

### output

241

## Lời giải
Gọi $dp_{ij}$ tổng khoảng cách nhỏ nhất của 2 robot mà Cuội đang ở vị trí khách i và Bờm đang ở vị trí vị khách j. (Và với trạng thái quy hoạch động như trên đảm bảo đã 2 robot đã phục vụ hết các vị khách từ 1 tới max(i, j)).
- Đầu tiên ta duyệt qua từng vị khách, chọn xem Cuội hay Bờm sẽ phục vụ vị khách này.
- Giả sử gọi vị khách ta đang xét là vị khách thứ k. Nếu Cuội phục vụ vị khách này và Bờm đang ở vị trí của vị khách j thì ta sẽ có trạng thái là $dp_{kj}$ , với trạng thái này ta có 2 trường hợp:
- j = k - 1, tức là vị khách thứ k - 1 do Bờm phục vụ, vậy trước đó nếu Cuội có phục vụ vị khách nào nữa thì chắc chắn vị khách đó < k - 1. Vậy $dp_{kj}$ = min($dp_{lj})$ + distance(l, k) với $\forall$ l < j - 1 nếu j = k - 1. (distance(l, r) là khoảng cách từ vị khách l tới vị khách r, lưu ý trường hợp l = 0).
- j < k - 1, vì các vị khách từ 1 tới max(k, j) đã được phục vụ mà j < k - 1, vậy suy ra vị khách thứ k - 1 do Cuội phục vụ. Vậy $dp_{kj}$ = $dp_{(k - 1)j}$ + distance(k - 1, k).

- Tương tự nếu cho Bờm phục vụ vị khách thứ k và Cuội đang ở vị trí của vị khách j thì sẽ có trạng thái là dp[j][k] và công thức truy hồi sẽ tương tự như trên.

Vậy kết quả sẽ là min(min($dp_{nj}$), min($dp_{jn}$)) với $\forall$ j $\leq$ n.

## Code minh họa

void komasan() {

	cin >> n;	
	cin >> xt >> yt;
	cin >> xs >> ys;

	for (int i = 1; i <= n; i++)
		cin >> x[i] >> y[i];

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			dp[i][j] = INF;

	dp[0][0] = 0;
	dp[1][0] = sqrt((x[1] - xt) * (x[1] - xt) + (y[1] - yt) * (y[1] - yt));
	dp[0][1] = sqrt((x[1] - xs) * (x[1] - xs) + (y[1] - ys) * (y[1] - ys));

	for (int i = 1; i <= n; i++) {

		x[0] = xt;
		y[0] = yt;

		for (int j = i - 2; j >= 0; j--)
			dp[i][j] = dp[i - 1][j] + sqrt((x[i] - x[i - 1]) * (x[i] - x[i - 1]) + (y[i] - y[i - 1]) * (y[i] - y[i - 1]));

		for (int j = i - 2; j >= 0; j--)
			dp[i][i - 1] = min(dp[i][i - 1], dp[j][i - 1] + sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])));

		x[0] = xs;
		y[0] = ys;

		for (int j = i - 2; j >= 0; j--)
			dp[j][i] = dp[j][i - 1] + sqrt((x[i] - x[i - 1]) * (x[i] - x[i - 1]) + (y[i] - y[i - 1]) * (y[i] - y[i - 1]));

		for (int j = i - 2; j >= 0; j--)
			dp[i - 1][i] = min(dp[i - 1][i], dp[i - 1][j] + sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])));
	
	}

	long double res = INF;
	for (int i = 0; i < n; i++) {

		res = min(res, dp[n][i]);
		res = min(res, dp[i][n]);

	}

	cout << (int)res;

}