{"code":"xedien","name":"Xe điện","description":"Một xe chạy bằng điện EV mới được sử dụng thay thế cho các xe nhiên liệu truyền thống. Có $n$ thành phố trên một mặt phẳng, với hai thành phố bất kì sẽ có một con đường nồi chúng. Giả sử hai thành phố $A$ và $B$ có tọa độ là $(a, b)$ và $(c, d)$ thì khoảng cách giữa hai thành phố này $d(A, B) = |a - c| + |b - d|$. Để dễ hình dung, ta coi mỗi đơn vị di chuyển EV sẽ tiêu tốn đúng 1 đơn vị nhiêu liệu điện. Mỗi thành phố có một trạm nạp điện cho xe, thành phố $A$ sẽ có chi phí $c(A)$ cho một đơn vị nhiên liệu điện. Nếu xe EV tại thành phố A đang không có đơn vị nhiên liệu nào muốn di chuyển đến thành phố $B$ thì nó phải mất chi phí nhỏ nhất là $c(A)\\times d(A, B)$ để có thể di chuyển từ $A$ đến $B$.\r\n\r\nATM phải di chuyển từ thành phố $S$ đến thành phố $T$ bằng xe EV của anh ấy. Ban đầu chiếc xe này đang không có nhiên liệu nào. Và chiếc xe này có thể nạp đầy được $W$ nhiên liệu hay chiếc EV này không thể chứa nhiều hơn $W$ nhiện liệu một lúc. Do đó nó không thể di chuyển được giữa hai thành phố có khoảng cách lớn hơn $W$. Ngoài ra ATM chỉ cho phép nạp tối đa $p$ lần nạp điện kể cả lần nạp đầu tiên.\r\n\r\n![enter image description here][1]\r\n\r\nCho biết tọa độ của $n$ thành phố và $S, T$, chi phí nạp nhiên liệu tại mỗi thành phố, $W$ và $p$, hãy tính chi phí nhỏ nhất để có thể đi được từ $S$ đến $T$.\r\n\r\n<h4>Input</h4>\r\n\r\n- Dòng đầu tiên chứa số nguyên $n$ ($1 < n\\le 1000$).\r\n- $n$ dòng tiếp theo mỗi dòng chứa 3 số nguyên $a, b, c$ là tọa độ và chi phí của các thành phố ($0\\le a, b\\le 10^6, 1\\le c\\le 10^4$). Trong đó dòng đầu tiên là thành phố $S$, dòng thứ hai là thành phố $T$.\r\n- Tiếp theo chứa số nguyên $W$ ($1\\le W\\le 10^5$).\r\n- Dòng cuối cùng chứa số nguyên $p$ ($1\\le p\\le 10$).\r\n\r\n\r\n<h4>Output</h4>\r\n\r\n- Ghi ra chi phí nhỏ nhất, hoặc ghi ra -1 nếu không thể đi được từ $S$ đến $T$.\r\n\r\n<h4>Example</h4>\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        5\r\n        1 1 4\r\n        3 3 3\r\n        1 3 4\r\n        2 2 5\r\n        3 1 3\r\n        3\r\n        2\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        14\r\n        ```\r\n\r\n!!! question \"Test 2\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        5\r\n        1 1 4\r\n        3 3 3\r\n        1 3 4\r\n        2 2 5\r\n        3 1 3\r\n        3\r\n        1\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        -1\r\n        ```\r\n\r\n!!! question \"Test 3\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        4\r\n        0 0 1\r\n        3 0 3\r\n        1 0 3\r\n        2 0 3\r\n        4\r\n        2\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        3\r\n        ```\r\n[1]: https://imgur.com/miOyPdU.png","points":400.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}