Carrers i avingudes P11225

Considereu un barri com Manhattan, on els carrers són “horitzontals” (en la direcció est-oest), i les avingudes són “verticals” (en la direcció sud-nord). Els carrers i avingudes s’etiqueten amb números a partir d’1: els carrers d’est a oest, i les avingudes de sud a nord. Així, cada cruïlla es pot identificar amb un parell (c, a). Per exemple, la cruïlla més avall i més a la dreta del mapa s’identifica amb el parell (1, 1).

Us trobeu a la cruïlla (c₁, a₁) i heu d’anar a la cruïlla (c₂, a₂). Quantes travessies haureu de caminar, si ho feu de forma òptima? Per exemple, si us trobeu a (23, 7) i heu d’anar fins a (42, 4), podeu primer moure-us a (30, 7) amb cost 7, després anar a (30, 4) amb cost 3, i finalment a (42, 4) amb cost 12. El cost total és 7 + 3 + 12 = 22. Es pot veure que aquest cost no es pot millorar.

Entrada

L’entrada consisteix en quatre línies, amb c₁, a₁, c₂ i a₂. Tots els nombres estan entre 1 i 1000.

Sortida

Escriviu una línia amb el cost mínim d’anar de la posició inicial a la final.